Need help in proving greedy for Movie Festival 2 (CSES Problem)

Правка en1, от parveen1981, 2023-01-07 20:57:43

Hi guys, I have been trying really hard for 15-20 days to prove the greedy algorithm for Movie Festival 2 but I am not able to do so and couldn't find a good proof on internet (I even tried chatGPT lol).

I was trying to go for greedy stays ahead technique. We can take the measurements as an array containing the ending time of movies for group members (sorted in ascending order each time a movie is added). For example: let $$$[t_1, t_2, ..., t_k]$$$, $$$[t_1', t_2', ..., t_k']$$$ be arrays in greedy and optimal approach with $$$t_i \leq t_i'$$$.

The base case was fairly easy, but I am having problem in proving that after k steps, if we can add a movie to optimal solution, then we can also add a movie to the greedy solution so that our measurement inequality still holds.

Can someone please help me with this? Thanks in advance.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский parveen1981 2023-01-07 20:57:43 938 Initial revision (published)