i_love_vim's blog

By i_love_vim, history, 4 days ago, In English

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
 
 
 
 
  • Vote: I like it
  • -6
  • Vote: I do not like it

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by i_love_vim (previous revision, new revision, compare).

»
4 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

4 2  
1 5  
1 3  
4 12  
8 10