arham___khan's blog

By arham___khan, history, 4 weeks ago, In English

This is the following problem. CSES Problem Set Movie Festival II This is my approach (https://cses.fi/paste/4d6196360ee8fd8e21094e/) It's failing a few cases I wanted to know if my approach is completely wrong or I'm not handling some cases properly.

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

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

I am not sure about the proof, but sort intervals by their end time , then greedily assign the Interval to the member who is currently free,and change his status from free to busy, now when the interval of that person ends you can count that person as free to watch again.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it
  • The mistake that you are making is that you just consider the earliest person that started watching a film. What could happen is that might assign a new movie to a person which has been free from some time but that could come in handy later on.

  • Example:

4 2

5 6

4 9

10 12

7 14

Now, according to your algorithm, the following would happen-

  1. You will assign one person to watch the first movie (5, 6).

  2. You will assign the next person to watch the second movie (4, 9).

  3. Now, you will see that the first person is free, so you will assign the first person to watch the third movie (10, 12).

  4. Now, the fourth movie cannot be watched by anyone. So the answer according to you is 3.

  • The actual answer however is 4 as if you assign the second person to watch the third movie, then the first person can also watch the 4th movie.

  • You should keep a track of the active movie watchers in a multiset instead of a queue and take the nearest option instead of taking the first person in the queue. I am attaching my code for your reference.

struct Event{
    int start_time, end_time;
};
bool cmp(Event &a, Event &b){
    if(a.end_time != b.end_time){
        return a.end_time < b.end_time;
    }
    return a.start_time < b.start_time;
}
int main(){
    int n, k;
    cin >> n >> k;
    vector e(n);
    for(int i = 0; i < n; i++){
        cin >> e[i].start_time >> e[i].end_time;
    }
    multiset free;
    sort(e.begin(), e.end(), cmp);
    for(int i = 1; i <= k; i++){
        free.insert(0);
    }
    for(auto x : e){
        auto it = free.lower_bound(x.start_time);
        if(it == free.end()){
            it--;
        }
        if(it == free.begin() && *it > x.start_time){
            n--;
            continue;
        }
        if(it != free.begin() && *it > x.start_time){
            it--;
        }
        free.erase(it);
        free.insert(x.end_time);
    }
    cout << n << "\n";
    return 0;
}