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.
I think this maybe helps
it just gives the algorithm, not the proof why it's optimal. But thanks btw.
Maybe we can think in this way:
Let's say we have a sequence of movies produced by any optimal solution. Now, if we can prove that we can produce same or better answer using our algorithm, we can say that our greedy solution is just as good or even better than optimal solution.
$$$Member_1: M_{1,1}, M_{1,2}, ..., M_{1,{x_1}}$$$
$$$Member_2: M_{2,1}, M_{2,2}, ..., M_{2,{x_2}}$$$
.
.
.
$$$Member_k: M_{k,1}, M_{k,2}, ..., M_{k,{x_k}}$$$
Let the sequence of movies is $$$S_1, S_2, ..., S_{optimalAns}$$$ where $$$optimalAns = x_1 + x_2 + ... + x_k$$$
Now let's say $$$i$$$ is the lowest index at which optimal sequence differs from our greedy sequence and let's say $$$S_i = M_{a,b}$$$. Now, there are 2 cases here:
Case #1. $$$M_{a,b}$$$ has least ending from all the movies available, but $$$Member_a$$$ doesn't have the greatest ending time of previous movie. And let's say $$$Member_u$$$ has the greatest ending time of previous movie at this point with some movie $$$M_{u,v-1}$$$ who is still available for movie $$$M_{a,b}$$$ i.e. $$$e_{u,v-1} \leq s_{a,b}$$$, where $$$e_{m,n}$$$ & $$$s_{m,n}$$$ are ending & starting times of some movie $$$M_{m,n}$$$. So in this case, we can replace sequence of $$$Member_a$$$ & $$$Member_u$$$ from movies $$$M_{a,b}$$$ and $$$M_{u,v}$$$ and our answer won't change. Essentially, sequence of members $$$a$$$ & $$$u$$$ will look like this:
$$$Member_a: M_{a,1}, ..., M_{a,b-1}, M_{u,v}, M_{u,v+1}, ..., M_{u,{x_u}}$$$
$$$Member_u: M_{u,1}, ..., M_{u,v-1}, M_{a,b}, M_{a,b+1}, ..., M_{a,{x_a}}$$$
Hence, in this case answer produced by greedy algorithm is just as good or even better since there is a chance that we can insert some more movies before $$$M_{u,v}$$$ in $$$Member_a$$$.
Case #2. $$$M_{a,b}$$$ doesn't have least ending from all the movies available, so in this case we can simply replace this movie with some movie with lesser ending time and repeat what we did in case 1. And we will get same or even better answer.
So, in both cases, we can see that our greedy algorithm produce just as good or even better answer than any other optimal solution. So our greedy algorithm must produce the optimal answer.
I hope this helps. Please let me know if there are any mistakes in my proof.