Hello all,
I am trying to solve CSES movie festival II using the same logic for movie festival I. I am greedily assigning the movies to k people sorted by end times. But this is giving me WA on cases 5, 6, and 7. These cases have n = 200000, so I cannot work them out on paper to find out the problem in my logic. So request to please give me some test cases to help me find the mistake in my logic.
My code
Spoiler
Problem link is 1632
Greedy. We process films in order of end time. For every film, if no person is free at start time, we dont watch that film. If at least one person free, we use the one latest free. Repeat.
We need to maintain a list/queue of persons with their times when they get available to watch the next film. Initially all persons are available at time 0.
Hi spookywooky!
Are you sure that list/queue (linear data structure) is enough and no need for set/multiset/pq?
You are right, since we need to query the one latest free from the list/queue we need some sort of priority queue.
whats the proof that this is optimal?
We process the films in the order of first end, that means we find the max number of watched films of a non increasing interval. Obviously we cannot watch more than the films that exist in that interval. So, foreach film we can watch it or not watch it. If we can watch the film it is allways optimal to do so since we cannot get a better result by not watching a film. "Can watcht the film" means that there is a person available at start of the film. If there is more than one person available it is always optimal to choose the person latest available, because again, we cannot get a better result by choosing another person.
Why is it always optimal to choose the latest person available? I cannot understand why that is optimal (Why can't we remove the element at the 0th place in case of a tie)?
Formally, why
ms.erase(--it)
instead ofms.erase(ms.begin())
??did you figure out why do we need to choose the latest person? I am stuck at same problem and can't figure out why it works like that only?
NO
Consider this case:
Person 1 will watch the first movie (from time 1 until time 2) and Person 2 will watch the second movie (from time 1 to time 5). When you decide who should watch the third movie (which starts at time 6) both persons are available again. But you have to choose the one that is available later, in this case person 2, then person 1 is free to watch the forth movie. If person 1 watches the third movie no one would be able to watch the forth movie.
Choosing the latest person always ensures that the remaining persons are available earlier and therefore have the most potential to watch more movies.
(For future reference)
A sample TC for which my logic will give WA is->
did you get accepted ?
You can see this: https://cses.fi/paste/bc4c79f7eee4db012401f1/
It can be easier like this: