Interval Scheduling

Before we start

This pattern is closely related to Merge Intervals, but the goal is completely different. Instead of combining intervals, we are selecting them — picking the most we can without any two overlapping. By the end you will be able to:

• See why sorting by end time (not start time!) is the magic move.
• Explain the greedy argument: why taking the earliest-finishing event is always at least as good as any other choice.
• Apply the pattern to removal-count and room-allocation problems.

Stop at every Pause & Think box.

Picture this first (no code yet)

Rock:     10:00 – 14:00
Jazz:     09:00 – 11:00
Pop:      11:00 – 13:00
Classical:12:00 – 16:00
Folk:     13:00 – 15:00
Blues:    14:00 – 16:00

That festival-goer's instinct — always grab the concert that ends the soonest — is the Interval Scheduling Maximisation algorithm.

The actual problem

Given a list of intervals [start, end], find the maximum number of non-overlapping intervals you can select.

Equivalently: what is the minimum number of intervals to remove so that no two overlap? (Same answer — they're complementary.)

input  = [[1,2],[2,3],[3,4],[1,3]]
output = 3   (select [1,2],[2,3],[3,4]; remove [1,3])

First, the slow way (so you feel the pain)

The obvious attempt: try every possible subset of intervals, check which subsets are non-overlapping, find the largest.

n = 10 intervals  →  2^10 = 1,024 subsets to check
n = 20 intervals  →  2^20 = 1,048,576 subsets
n = 30 intervals  →  2^30 = 1,073,741,824 subsets  (one billion!)

Exponential blowup. Completely impractical.

Even dynamic programming gives O(n²). The greedy approach gives O(n log n) — dominated by sorting. One pass after the sort is O(n).

The turning point

Intervals: [1, 10], [2, 3], [3, 5]

With Strategy A: [1,10] is picked. Its end is 10. Both [2,3] and [3,5] start before 10 — both blocked. Total selected: 1.

With Strategy B: [2,3] is picked (ends earliest at 3). Next, [3,5] starts at 3 ≥ 3 — pick it. Total selected: 2.

Strategy B wins here, and it always wins (or ties). Here's the intuition: picking the earliest-ending interval leaves the maximum remaining time for future intervals. Choosing anything else can only reduce (or at best equal) the remaining time.

The one idea to remember

Watch it happen, frame by frame

Input sorted by end time: [[1,2],[1,3],[2,3],[3,4]]

last_end = -∞  (nothing picked yet)
count = 0

interval [1,2]: start=1 ≥ -∞?  YES → pick it.  last_end=2, count=1
interval [1,3]: start=1 ≥ 2?   NO  → skip (overlaps).
interval [2,3]: start=2 ≥ 2?   YES → pick it.  last_end=3, count=2
interval [3,4]: start=3 ≥ 3?   YES → pick it.  last_end=4, count=3

Maximum non-overlapping intervals = 3  ✅
([1,2],[2,3],[3,4] — touching counts as non-overlapping here)

Sorted by end: [[1,4],[3,5],[0,6],[5,7],[4,8]]

last_end=-∞, count=0
[1,4]: 1 ≥ -∞  →  pick. last_end=4, count=1
[3,5]: 3 ≥ 4?  NO  →  skip.
[0,6]: 0 ≥ 4?  NO  →  skip.
[5,7]: 5 ≥ 4?  YES →  pick. last_end=7, count=2
[4,8]: 4 ≥ 7?  NO  →  skip.

Maximum = 2 ([1,4] and [5,7])

Now, the code — line by line

def eraseOverlapIntervals(intervals):
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[1])    # sort by END time — this is the key

    count = 1                              # we always pick the first interval
    last_end = intervals[0][1]            # end time of the last interval we picked

    for start, end in intervals[1:]:      # sweep from second onward
        if start >= last_end:             # no overlap: this interval starts after last picked ends
            count += 1                    # pick it
            last_end = end               # update the "last picked" end time

    return len(intervals) - count         # intervals to REMOVE = total - maximum we can keep

Line by line with the festival story:

• intervals.sort(key=lambda x: x[1]) — sort concerts by finish time.
• count = 1, last_end = intervals[0][1] — the earliest-finishing concert is always our first pick.
• if start >= last_end: — this concert starts after the previous one ended (or exactly when it ended — they don't overlap).
• count += 1; last_end = end — attend it; update when the stage is free next.
• return len(intervals) - count — we asked for removals; total minus kept = removed.

Why does the greedy choice work?

The argument is called an exchange argument — one of the most useful proof techniques in algorithms.

Claim: If an optimal solution doesn't start with the earliest-ending interval E, we can swap whatever it does start with (call it X) for E, and the solution remains valid with the same count.

Proof: E ends at or before X ends (we chose E as earliest-ending). So swapping X out and putting E in cannot create a new overlap — E finishes earlier, so the next interval in the solution fits just as well or better. The count doesn't decrease.

Since we can always swap in the earliest-ending choice without losing anything, there is always an optimal solution that makes the greedy choice first. By induction, making the greedy choice at every step is optimal.

Why is it so fast?

Sort: O(n log n). Sweep: O(n) — one pass, constant work per interval. Total: O(n log n).

n = 100,000  →  ~1,700,000 sort ops + 100,000 sweep ops
               vs. ~10,000,000,000 for DP approaches

When should I reach for this? (the trigger list)

• Problem asks to select the maximum number of non-overlapping intervals.
• Equivalently: minimum removals to make intervals non-overlapping.
• Equivalently: maximum number of events one person can attend.
• Keywords: "non-overlapping intervals," "activity selection," "meeting schedule."
• The key smell: you need to maximise count of selections, not cover a range.

Sort by end time. This distinguishes interval scheduling from Merge Intervals (sort by start).

The same trick in three disguises

Disguise 1 — Non-overlapping Intervals (LC #435)

Minimum intervals to remove. Sort by end, greedily pick non-overlapping, return total - count.

Disguise 2 — Minimum Number of Arrows to Burst Balloons (LC #452)

Balloons = intervals on a number line. An arrow at position x bursts every balloon [start, end] where start ≤ x ≤ end. Minimum arrows = minimum "groups" of non-overlapping intervals — exactly the maximum non-overlapping count.

def findMinArrowShots(points):
    points.sort(key=lambda x: x[1])    # sort by end
    arrows = 1
    arrow_pos = points[0][1]           # shoot at the earliest end

    for start, end in points[1:]:
        if start > arrow_pos:          # this balloon is not hit by current arrow
            arrows += 1
            arrow_pos = end            # new arrow at this balloon's end
    return arrows

Same greedy structure. The "arrow" is the last_end tracker.

Disguise 3 — Meeting Rooms — Maximum Rooms Needed (LC #253)

How many rooms do you need to host all meetings? This is not interval scheduling maximisation — it's measuring peak concurrency. (Covered in Merge Intervals.) Bringing it up here because students confuse them: scheduling maximisation = greedy by end time; room minimisation = min-heap by end time.

import bisect

def jobScheduling(startTime, endTime, profit):
    jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
    dp = [[0, 0]]   # [end_time, max_profit_up_to_here]

    for s, e, p in jobs:
        # find latest job that ends at or before s
        i = bisect.bisect_right(dp, [s, float('inf')]) - 1
        if dp[i][1] + p > dp[-1][1]:
            dp.append([e, dp[i][1] + p])

    return dp[-1][1]

Traps that catch beginners

Say it like a pro (interview one-liner)

"This is interval scheduling maximisation. I'll sort by end time, then greedily pick each interval as long as it starts at or after the last-picked interval ends. Sorting by end is the key — it always leaves the most room for future intervals. O(n log n) total, O(1) extra space after the sort."

For the minimum-removals variant:

"Same algorithm — I count how many I can keep and subtract from total."

Check yourself

Practice problems

When you can solve LC #435 from memory and explain why end-time sorting beats start-time sorting, you've learned this pattern.

Next up: Cyclic Sort — a completely different flavour where we exploit the fact that numbers in range 1..N tell you exactly where they belong, and use that to sort in O(n) with zero comparisons.