DSA sheet / Sorting and searching
Movie Festival
Do these first: Restaurant Customers
The problem in brief
There are n movies (up to 200 000), each with a start and end time. You watch each chosen movie in full and cannot watch two at once. Print the maximum number of movies you can watch.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1629.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
You are choosing a set of non-overlapping intervals. Think of a rule for which interval to lock in first.
-
Try three greedy rules on small examples: earliest start, shortest movie, earliest finish. Draw a counterexample for each rule that fails.
-
The winner is the one that keeps the most room for the future. Which of the three leaves the largest amount of time still available after your first choice?
-
After picking the first movie, what condition must the next one satisfy, and how do you skip all the movies that conflict?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
Interval scheduling is the textbook example of a greedy algorithm proven by an exchange argument. Brute force over subsets is exponential, and a DP over time is impossible with times up to 10^9, so a greedy is the only realistic route. The skill is choosing the right greedy criterion.
“Earliest start” fails (a very long movie starting first blocks everything). “Shortest” fails (a short movie in the middle can block two others). “Earliest finish” works: among all movies you could watch first, the one that ends soonest leaves the maximum remaining time, and any solution that starts with a different movie can swap its first movie for this one without losing anything, because the earliest-ending movie finishes no later.
The habit: when unsure which greedy criterion is right, look for counterexamples to the tempting ones and then prove the survivor by the exchange argument.
Intuition
At every step, pick whichever movie lets you get out of the cinema soonest. Then you are back to the same problem with a shorter timeline. Repeating that never paints you into a corner.
Approach
- Sort the movies by end time.
- Keep
lastEnd(initially 0 or minus infinity). For each movie in that order: if its start is at leastlastEnd, watch it: count it and setlastEndto its end. - Print the count.
Tie rule: a movie that starts exactly when the previous one ends is allowed (start >= lastEnd). Pitfalls: sort by end time, not start; movies with the same end are interchangeable for this algorithm; times up to 10^9 fit in 32-bit ints.
Complexity
O(n log n) time for the sort, O(n) for the sweep; O(n) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<pair<int, int>> mv(n); // (end, start): sorting orders by end time
for (auto &m : mv) cin >> m.second >> m.first;
sort(mv.begin(), mv.end());
int count = 0, lastEnd = 0;
for (auto &m : mv) {
if (m.second >= lastEnd) {
count++;
lastEnd = m.first;
}
}
cout << count << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
movies = sorted((int(data[2 + 2 * i]), int(data[1 + 2 * i])) for i in range(n)) # (end, start)
count = 0
last_end = 0
for end, start in movies:
if start >= last_end:
count += 1
last_end = end
print(count)
main()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
long[] key = new long[n]; // end in the high bits, start in the low 30: sorts by end time
for (int i = 0; i < n; i++) {
st.nextToken();
long a = (long) st.nval;
st.nextToken();
long b = (long) st.nval;
key[i] = (b << 30) | a;
}
Arrays.sort(key);
int count = 0;
long lastEnd = 0;
long mask = (1L << 30) - 1;
for (long k : key) {
long start = k & mask, end = k >> 30;
if (start >= lastEnd) {
count++;
lastEnd = end;
}
}
System.out.println(count);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const movies = [];
for (let i = 0; i < n; i++) movies.push([data[1 + 2 * i], data[2 + 2 * i]]);
movies.sort((p, q) => p[1] - q[1]); // by end time
let count = 0;
let lastEnd = 0;
for (const [start, end] of movies) {
if (start >= lastEnd) {
count++;
lastEnd = end;
}
}
console.log(count);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).