Greedy Interval Scheduling: Why You Sort by End Time

Greedy algorithms make the choice that looks best right now and never go back. Sometimes that works perfectly and sometimes it fails badly. Interval scheduling is the classic case where it works, and it is a great example for learning how to prove that a greedy choice is correct rather than just hoping.

The problem

There are n movies at a festival. Movie i starts at time s_i and ends at time e_i. You can only watch one movie at a time, and you must watch each one from start to finish. A movie may start at the exact moment another one ends. What is the largest number of movies you can watch? This is CSES 1629 – Movie Festival, with n up to 2 × 10⁵.

Greedy ideas that do not work

• Earliest start first. A very long movie that starts first would block everything else.
• Shortest movie first. A short movie can sit right across the boundary of two longer movies that would otherwise both fit, so choosing it costs you two.

Trying to break your own greedy idea with small examples like these is the most useful habit for greedy problems.

The rule that works: earliest end first

Sort movies by end time. Go through them in that order, and watch a movie whenever it starts after (or exactly when) the last chosen movie ended.

The intuition is that finishing early leaves as much of the day free as possible for everything that comes after.

Why it is correct (exchange argument)

Take any optimal schedule and look at its first movie. Our greedy picks the movie with the earliest end time overall. That greedy movie ends no later than the optimal schedule's first movie, so we can swap it in. The rest of the optimal schedule still fits, because everything in it starts after the old first movie ended, which is no earlier than when the greedy movie ends.

So there is an optimal schedule that begins with the greedy choice. Remove that movie and everything that overlaps it, and the same argument applies to the rest. By repeating this, the greedy schedule is as long as an optimal one.

Code (C++)

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

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> movies(n);   // stored as (end, start)
    for (auto &[e, s] : movies) cin >> s >> e;

    sort(movies.begin(), movies.end());  // earliest end time first

    int watched = 0;
    int free_at = 0;                     // when we are next free
    for (auto [e, s] : movies) {
        if (s >= free_at) {
            watched++;
            free_at = e;
        }
    }
    cout << watched << '\n';
    return 0;
}

Storing each pair as (end, start) means the default sort orders by end time, with no custom comparator needed.

Example

3
3 5
4 9
5 8

Sorted by end time: (3, 5), (5, 8), (4, 9). We watch 3–5, then 5–8 (it starts right as the first ends), and skip 4–9 because it starts before 8. Answer: 2.

Complexity

Sorting is O(n log n) and the scan is O(n).

Be careful with the boundary

Whether a movie may start exactly when the previous one ends decides between >= and >. Read the statement for that detail every time. Getting it wrong passes the samples surprisingly often and then fails on hidden tests.

Related problems

• Minimum number of points to hit every interval. Same sorting, and the same proof idea: place a point at the end of the earliest-ending interval not yet hit.
• Minimum rooms so that every meeting fits. Different greedy: sort by start time and track when rooms become free, usually with a priority queue.

Practice problems

• CSES 1629 – Movie Festival: the problem from this post.
• CSES 1630 – Tasks and Deadlines: another “sort, then sweep” greedy with a short exchange-argument proof.

If you are newer to proofs like this, Domino Piling (50A) uses the same “upper bound plus construction” style of reasoning in a simpler setting.