Skip to content

Interval Scheduling

A Different Kind of Proof

The exchange argument (Chapter 2) works like this: take any optimal solution, find two adjacent elements in the wrong order, swap them, show things don't get worse. Repeat until you reach the greedy order.

Greedy stays ahead is different. Instead of starting with an optimal solution and transforming it, you directly prove that the greedy solution is at least as good as any other solution at every step.

The proof structure: 1. Define a "state" at step \(k\) (e.g., the end time of the \(k\)-th selected item) 2. Claim: greedy's state at step \(k\) \(\leq\) optimal's state at step \(k\) (greedy finishes earlier) 3. Prove by induction on \(k\)

If greedy's state is always at least as good as optimal, greedy can always do at least as well as optimal.

The Problem That Defines the Technique

CSES 1629 — Movie Festival: \(n\) movies with start and end times. You can watch a movie only if you're free for its entire duration. Maximize the number of movies watched.

The Greedy Choice: Always pick the movie that finishes earliest. Ending sooner leaves the maximum possible room for future movies.

Interval scheduling: sorting by end time and selecting non-overlapping intervals greedily

The key observation: you want to leave as much time free as possible after each movie. Ending early = more future options.

Greedy: sort by end time, always pick the next movie that starts after the current one ends.

Let's see what happens with a bad sort order first.

What Breaks If You Sort Wrong

Movies: (1,4), (2,3), (3,5), (4,6) — displayed as (start, end).

Sort by start time, pick earliest-starting non-overlapping: - Pick (1,4). Now need start \(\geq 4\). - (2,3) starts at 3 < 4. Skip. - (3,5) starts at 3 < 4. Skip. - (4,6) starts at 4 \(\geq\) 4. Pick. - Total: 2 movies.

Sort by duration (shortest first):

Durations: (2,3) → 1, (4,6) → 2, (3,5) → 2, (1,4) → 3. Sorted: (2,3), (4,6), (3,5), (1,4). - Pick (2,3). Need start \(\geq 3\). - (4,6) starts at 4 \(\geq\) 3. Pick. Need start \(\geq 6\). - (3,5) starts at 3 < 6. Skip. - (1,4) starts at 1 < 6. Skip. - Total: 2 movies.

Sort by end time (our greedy):

Sorted: (2,3), (1,4), (3,5), (4,6). - Pick (2,3). Need start \(\geq 3\). - (1,4) starts at 1 < 3. Skip. - (3,5) starts at 3 \(\geq\) 3. Pick. Need start \(\geq 5\). - (4,6) starts at 4 < 5. Skip. - Total: 2 movies.

All three give 2 here. Now try a case where end-time sorting wins.

Movies: (1,3), (2,4), (3,5), (4,6), (1,2), (5,6).

Sort by end time: (1,2), (1,3), (2,4), (3,5), (4,6), (5,6). - Pick (1,2). Need start \(\geq 2\). - (1,3) starts at 1 < 2. Skip. - (2,4) starts at 2 \(\geq\) 2. Pick. Need start \(\geq 4\). - (3,5) starts at 3 < 4. Skip. - (4,6) starts at 4 \(\geq\) 4. Pick. Need start \(\geq 6\). - (5,6) starts at 5 < 6. Skip. - Total: 3 movies.

Sort by start time: (1,2), (1,3), (2,4), (3,5), (4,6), (5,6). - Pick (1,2). Need start \(\geq 2\). - (1,3) starts at 1 < 2. Skip. - (2,4) starts at 2 \(\geq\) 2. Pick. Need start \(\geq 4\). - (3,5) starts at 3 < 4. Skip. - (4,6) starts at 4 \(\geq\) 4. Pick. Need start \(\geq 6\). - (5,6) starts at 5 < 6. Skip. - Total: 3 movies. (Ties with end-time here.)

End-time sorting is provably optimal — the other methods aren't. The proof below shows exactly why.

The Stays-Ahead Proof

Let greedy's movies be \(g_1, g_2, \ldots, g_k\) (sorted by end time, as picked). Let OPT's movies be \(o_1, o_2, \ldots, o_m\) (any valid selection, sorted by end time).

Claim: \(\text{end}(g_i) \leq \text{end}(o_i)\) for all \(i \leq \min(k, m)\).

Base case (\(i=1\)): Greedy picks the movie with the earliest end time. OPT picks some movie \(o_1\). Since greedy picks the globally earliest-ending movie: \(\text{end}(g_1) \leq \text{end}(o_1)\). ✓

Inductive step: Assume \(\text{end}(g_i) \leq \text{end}(o_i)\). We need to show \(\text{end}(g_{i+1}) \leq \text{end}(o_{i+1})\).

OPT's movie \(o_{i+1}\) starts after \(o_i\) ends: \(\text{start}(o_{i+1}) \geq \text{end}(o_i) \geq \text{end}(g_i)\).

So \(o_{i+1}\) is a valid option for greedy at step \(i+1\) (it starts after greedy's last movie ended). But greedy picks the earliest-ending available movie, so:

\[\text{end}(g_{i+1}) \leq \text{end}(o_{i+1}) \quad \checkmark\]

Conclusion: Since greedy is always "ahead" (finishes each movie no later than OPT finishes its \(i\)-th movie), if OPT can pick \(m\) movies, greedy can pick at least \(m\) movies: \(k \geq m\). But OPT is optimal, so \(m \geq k\). Therefore \(k = m\): greedy is optimal.

Tracing the Algorithm

Movies: (1,4), (3,5), (0,6), (5,7), (3,8), (5,9), (6,10), (8,11).

Sort by end time: (1,4), (3,5), (0,6), (5,7), (3,8), (5,9), (6,10), (8,11).

Step Movie \((s,e)\) lastWatchedEnd \(s \geq\) lastWatchedEnd? Action moviesWatched
1 (1,4) -1 \(1 \geq -1\) ✓ Watch 1, last=4
2 (3,5) 4 \(3 \geq 4\) ✗ Skip 1
3 (0,6) 4 \(0 \geq 4\) ✗ Skip 1
4 (5,7) 4 \(5 \geq 4\) ✓ Watch 2, last=7
5 (3,8) 7 \(3 \geq 7\) ✗ Skip 2
6 (5,9) 7 \(5 \geq 7\) ✗ Skip 2
7 (6,10) 7 \(6 \geq 7\) ✗ Skip 2
8 (8,11) 7 \(8 \geq 7\) ✓ Watch 3, last=11

Answer: 3 movies.

Activity Selection vs Interval Piercing: Two Faces of the Same Algorithm

Interval Piercing (ABC103D, CF22D): Given intervals, find the minimum number of "points" such that every interval contains at least one point.

This is the dual of activity selection: - Activity selection: maximize intervals picked such that no two overlap. - Interval piercing: minimize points such that every interval is "hit."

Remarkably, both use the same greedy: sort by right endpoint, process left to right.

Problem What you do when right endpoint is reached
Activity selection If \(\text{start} \geq \text{lastEnd}\): pick this interval, update lastEnd
Interval piercing If \(\text{left} > \text{lastPoint}\): place a new point at right, record position

Trace interval piercing on [(1,3), (2,5), (4,6), (7,9)]:

Sorted by right: (1,3), (2,5), (4,6), (7,9).

Interval lastPointLocation \(\text{left} > \text{last}\)? Action
(1,3) \(-\infty\) \(1 > -\infty\) ✓ Place point at 3, last=3
(2,5) 3 \(2 > 3\) ✗ Point at 3 already covers it
(4,6) 3 \(4 > 3\) ✓ Place point at 6, last=6
(7,9) 6 \(7 > 6\) ✓ Place point at 9, last=9

3 points: {3, 6, 9}. Minimum.

Why the same sort? Both problems care about "how far right can we extend coverage." Sorting by right endpoint always confronts you with the most constrained (earliest-ending) interval first.

The Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int numMovies;
    cin >> numMovies;

    vector<pair<int, int>> movieIntervals(numMovies);
    for (int i = 0; i < numMovies; i++) {
        cin >> movieIntervals[i].first >> movieIntervals[i].second;
    }

    auto endTimeCompare = [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second < b.second;
    };
    sort(movieIntervals.begin(), movieIntervals.end(), endTimeCompare);

    int moviesWatched = 0;
    int lastWatchedEnd = -1;

    for (const auto& movie : movieIntervals) {
        int currentStart = movie.first;
        int currentEnd = movie.second;

        if (currentStart >= lastWatchedEnd) {
            moviesWatched++;
            lastWatchedEnd = currentEnd;
        }
    }

    cout << moviesWatched << "\n";
    return 0;
}

Data is stored naturally as {start, end}. The lambda endTimeCompare sorts by end time explicitly — no backward-storage tricks. This reinforces the custom comparator pattern from Chapter 2.

Try It

Fill in the empty if block: moviesWatched++; lastWatchedEnd = currentEnd;

Input:
4
3 5
4 9
5 8
2 7
Output: 2

Trace: sorted by end: (3,5), (2,7), (5,8), (4,9). - (3,5): start \(3 \geq -1\) ✓. Watch. last=5. - (2,7): start \(2 \geq 5\) ✗. Skip. - (5,8): start \(5 \geq 5\) ✓. Watch. last=8. - (4,9): start \(4 \geq 8\) ✗. Skip. Total: 2. ✓

Input:
3
1 5
2 3
4 5
Output: 2

Sorted by end: (2,3), (1,5), (4,5). - (2,3): pick. last=3. - (1,5): start \(1 \geq 3\) ✗. Skip. - (4,5): start \(4 \geq 3\) ✓. Pick. Total: 2.

Challenge: What happens if two movies have the same end time? Does the order between them matter? Can you construct a case where it does?

Problems

Problem Link Difficulty
CSES — Movie Festival cses.fi/problemset/task/1629 Medium
ABC103D — Islands War atcoder.jp/contests/abc103/tasks/abc103_d 400pts
CF22D — Segments codeforces.com/problemset/problem/22/D 1900