CSES - Movie Festival II

Explanation

The first step is the same as that of Movie Festival; sort the movies in increasing order of end time. For each movie in order, we will assign it to one of the $k$ members to watch (or none of them).

Keep track of the time each member finishes watching all of his currently assigned movies in an ordered multiset (represented by a TreeMap in Java or a multiset in C++). Initially, the collection consists of $k$ zeroes.

For each movie in order, we can assign a member to watch it if there exists an element in the sorted collection less than or equal to the start time of the movie. If there are multiple such elements, choose the greatest one (the member who finished watching his assigned movies the latest). Assign the member to watch this movie by incrementing the answer and updating the collection accordingly.

Implementation

Time Complexity: $\mathcal{O}(n\log k)$

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<pair<int, int>> v(n);

Copy
import java.io.*;
import java.util.*;

public class MovieFestival2 {
	public static void main(String[] args) {
		FastIO io = new FastIO();
		int n = io.nextInt();
		int k = io.nextInt();

		Interval[] movies = new Interval[n];