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**

Auto comment: topic has been updated by i_love_vim (previous revision, new revision, compare).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

latestfree. 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.

Thanks!

I also found this for better understanding the latest free part.

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 freefrom 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.

(For future reference)A sample TC for which my logic will give WA is->

did you get accepted ?