In this problem, we're asked the maximum number of movie intervals $(start,end)$ we can cover using $k$ people rather than $1$.

Main Idea

First, solve the one person variant of this problem. We can use the same approach and include multiple people instead of just one.

Whenever we come across a movie, we check if someone who previously watched a movie can watch this one too. If there are multiple people that can have this movie assigned, choose the latest one (that way if we encounter a movie that has an earlier start time, we can still assign that movie).

If the above condition doesn't hold and there are currently less than K people watching a movie, we can just assign a new person to this movie.

We can keep a hold of the people watching movies by storing it in some sort of collection, a multiset is used below.

Implementation using a multiset in C++:

1#include <iostream>
2#include <vector>
3#include <set>
4#include <algorithm>
5using namespace std;
6
7int n, k;
8vector<pair<int, int> > v(200005);
9
10int main() {