What Is the Interval Scheduling Algorithm? The Greedy Approach, Explained

Six talks at a conference. One you. Talks overlap and you can only be in one room at a time. You have limited time, infinite FOMO, and a laptop bag that already weighs too much. Which talks do you pick?

That's interval scheduling. It shows up constantly in coding interviews, usually disguised as meeting rooms or task scheduling. The solution is a greedy interval scheduling algorithm, under 10 lines to implement. The trick is understanding why it works, because interviewers will ask.

The Problem Has One Job

You have a list of activities. Each has a start time and an end time. Two activities conflict if they overlap. The goal: find the largest subset with no conflicts.

This is interval scheduling maximization, also called the activity selection problem. One of the cleanest greedy problems in all of CS.

Concrete example. Six talks today:

Talk	Start	End
A	9	11
B	9	14
C	11	13
D	12	15
E	13	16
F	14	17

Attending B blocks C, D, and E. You get in early, you get out late, you've burned the whole day on one talk. You could have learned so much. Instead you watched a guy read from his slides for five hours. Attending A, C, and E gives you three with no conflict. Can you do four? No combination of four works. Three is optimal.

Three Wrong Instincts (and Why They Fail)

Before the right algorithm, the wrong ones. Each sounds plausible. You've probably thought of at least two of them yourself, maybe with some confidence.

Earliest start time. Pick the activity that starts first, remove conflicts, repeat. Fails when one long early activity blocks several short later ones. An interval from 1 to 100 starts earliest, but attending it means you go home having seen one talk. You dragged yourself there at 9 AM for this.

Shortest duration. Pick the shortest activity, remove conflicts, repeat. Fails because a short interval can straddle two longer ones and waste time on both sides. Duration doesn't tell you where something sits on the timeline.

Fewest conflicts. Pick the activity with the fewest overlapping neighbors. Expensive to compute and still not optimal in general.

Each looks at the wrong property. The right one is where you finish.

Every wrong instinct in this section, distilled into one Stack Overflow thread.

Interval Scheduling Algorithm: Sort by Finish Time

The algorithm: sort all intervals by end time, then take each interval that doesn't conflict with the last one you picked.

That's it. An interval that finishes early leaves the most room on the remaining timeline. Get in, get out, leave space for what comes next.

Step through the example. Sorted by end time:

A (9-11), C (11-13), B (9-14), D (12-15), E (13-16), F (14-17)

• Take A. Last end = 11.
• C starts at 11 ≥ 11. Take it. Last end = 13.
• B starts at 9 < 13. Skip.
• D starts at 12 < 13. Skip.
• E starts at 13 ≥ 13. Take it. Last end = 16.
• F starts at 14 < 16. Skip.

Result: A, C, E. Three talks. Correct.

def max_non_overlapping(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])
    count = 0
    last_end = float('-inf')

    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end

    return count

No heap. No extra data structures. One pass after sorting. There's something almost annoying about how short it is.

The greedy interval scheduling algorithm, personified.

The boundary condition matters. Intervals are non-overlapping when one starts exactly when the other ends (start >= last_end). If the problem defines touching as a conflict, change to start > last_end. Read the problem statement before assuming.

Why Earliest Finish Time Wins: The Exchange Argument

The proof is a technique called an exchange argument. Suppose you have an optimal solution that doesn't start with the greedy choice (the interval with the smallest finish time). Call the greedy choice g and whatever the optimal solution starts with k.

Since g has the smallest finish time overall, g finishes no later than k. Swap k out, put g in. The resulting set has the same number of intervals and no new conflicts, because replacing a later-finishing interval with an earlier-finishing one never creates a new overlap with what follows. Any optimal solution can be transformed to start with the greedy choice, so the greedy choice is always safe.

Apply this argument recursively on the remaining subproblem and you have a full proof. Two sentences. No DP table.

See The Greedy Choice Property: One Test Separates Greedy from DP for more on when this kind of reasoning holds.

Time and Space

O(n log n) time, O(1) extra space. The sort dominates. The single pass afterward is O(n), and you track one integer. If you collect the actual selected intervals, that's O(k) where k is the count, but the algorithm itself doesn't require it.

This is effectively optimal. Any algorithm has to read all n intervals, and comparison sorting is O(n log n) in the worst case.

Four Interview Variants Worth Knowing

The core algorithm shows up in several disguises. Recognizing which variant you're looking at is half the problem.

Variant 1: Minimize removed intervals (LeetCode 435). What's the minimum number to remove to make them all non-overlapping? The complement of maximization: if you can keep k intervals, you remove n - k. Run the greedy algorithm, subtract from n. One-line twist on the function above.

Variant 2: Minimum groups (LeetCode 452, 253). Minimum Number of Arrows to Burst Balloons asks how many shots pierce every balloon. Meeting Rooms II asks how many rooms to host all meetings. Both equal the maximum depth of overlap at any point on the timeline. Different algorithm: sort by start time and use a min-heap of end times.

import heapq

def min_meeting_rooms(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[0])
    heap: list[int] = []

    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)
        else:
            heapq.heappush(heap, end)

    return len(heap)

The two algorithms look similar but solve entirely different problems. ISM asks how many you can attend. Interval partitioning asks how many rooms you need to host all of them. Mixing them up is one of the most common interval mistakes in interviews.

Variant 3: Weighted interval scheduling (LeetCode 1235). Each interval now has a profit. Maximize total profit, not count. Greedy fails here because one long high-value interval might beat several short low-value ones. You need DP with binary search: sort by end time, find the latest non-conflicting interval for each index, fill a DP table. Still O(n log n) but fundamentally different reasoning.

The tell: unweighted intervals and maximizing count means greedy. Weighted intervals and maximizing value means DP. See Dynamic Programming Is Just Recursion With a Memory for the setup.

Variant 4: Merge overlapping intervals (LeetCode 56). Not strictly scheduling, but the same sorting step appears. Sort by start time, then merge adjacent intervals that overlap. The Merge Intervals pattern is a prerequisite for nearly everything else in this family.

The Interview Pressure Point

Interval scheduling problems seem easy once you've seen them. The real test is explaining the greedy choice while coding, with someone watching you on a shared screen, in real time, while you try to remember if you left the stove on.

Interviewers routinely ask "why end time and not start time?" or "what breaks if you sort by duration?" The room goes quiet. You stare at code you know works. It's right there. But now you have to say why, out loud, in a complete sentence. These aren't gotcha questions. They probe whether you understand the algorithm or just memorized the sort key.

Practice saying this out loud: "The earliest-finishing interval leaves maximum room for future intervals. Any optimal solution that starts differently can be swapped to use the greedy choice without losing compatibility."

That sentence is worth having ready before you walk in. If you want to get comfortable explaining greedy reasoning under live interview conditions, SpaceComplexity runs voice-based mock interviews with rubric-based feedback. Saying "I sort by end time because..." out loud is a different skill from knowing it at your desk, and the gap shows in real interviews.

Key Takeaways

• Interval scheduling maximization: largest set of non-overlapping intervals. Greedy, O(n log n).
• Sort by end time. Earliest finish leaves maximum future room.
• Exchange argument: any optimal solution can be transformed to start with the greedy choice.
• Interval partitioning (min rooms, LeetCode 253) is a different problem. Sort by start, use a min-heap.
• Weighted intervals break greedy. Use DP with binary search (LeetCode 1235).
• Recognizing the variant is half the interview problem.

For more patterns in this family, Top Merge Intervals Problems covers 13 variations, and The Greedy Algorithm: When Local Optimal Means Global Optimal covers the broader class of problems where this reasoning applies.

Further Reading

• Interval Scheduling on Wikipedia
• Activity Selection Problem on Wikipedia
• Activity Selection Problem on GeeksforGeeks
• Greedy Algorithms lecture, Stanford CS161 (PDF)
• LeetCode 435: Non-overlapping Intervals