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 apporach 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++:

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int n, k;
vector<pair<int, int> > v(200005);

int main() {