Why Does Greedy Work for Interval Scheduling? Here's the Proof

Source: Dev.to

Originally published on LeetCopilot Blog

TL;DR

• Topic: Selecting the maximum number of non‑overlapping intervals using the earliest‑finish greedy.
• Why it matters: Interviews test whether you can justify the greedy choice, not just write a sorted loop.
• Core steps:
  1. Sort intervals by end time.
  2. Scan once, keeping intervals whose start ≥ lastEnd.
  3. Update lastEnd after each selection.
• Common confusion: Sorting by start time or forgetting to update the lastEnd boundary.
• You’ll learn: A picture‑friendly trace, a short proof idea, a minimal code snippet, and practice drills.

Beginner‑Friendly Explanation: Why Earliest Finish Wins

Intuition – Finishing sooner frees space for more intervals. Picking the earliest end time leaves the maximal remaining room.

Exchange argument – If you pick an interval that ends later than another compatible one, you can swap it for the earlier finisher without reducing the answer. (See the counter‑example habits in the article Greedy Algorithm Counterexamples for Coding Interviews.)

Boundary tracking – Maintain lastEnd, the end time of the last accepted interval, as your invariant.

Step‑by‑Step Learning Guidance

1. Sort by end time
   Sorting by start time is a common trap. Sorting by end time guarantees the swap argument works.

2. Walk once
   For each interval, if start >= lastEnd, select it and update lastEnd. This mirrors the monotonic‑pass discipline discussed in Greedy or DP for Coin Change Decisions.

3. Narrate the invariant
   Say: “lastEnd is the earliest finishing boundary among intervals chosen so far. I only accept intervals that start after it.”

4. Validate with a counterexample check
   Ensure no earlier‑finishing compatible interval was skipped. If found, swapping maintains or increases capacity, upholding correctness.

5. Practice with varied intervals
   Use overlapping, nested, and equal‑end cases to cement when updates occur.

Visualizable Example: Trace Table

Intervals (start, end) sorted by end:
[1,2], [2,3], [1,3], [3,4], [2,5]

Pick [1,2] → lastEnd = 2
Pick [2,3] (start >= lastEnd) → lastEnd = 3
Skip [1,3] (starts before lastEnd)
Pick [3,4] → lastEnd = 4
Skip [2,5] (starts before lastEnd)

Drawing horizontal bars helps you see compatibility quickly.

Code Example: Earliest‑Finish Greedy

def interval_scheduling(intervals):
    # Sort by end time
    intervals.sort(key=lambda x: x[1])
    chosen = []
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:          # compatible?
            chosen.append((start, end))
            last_end = end
    return chosen

The code tracks a single boundary and accepts intervals that start after it, embodying the invariant.

Practical Preparation Strategies

• Swap‑proof rehearsal: Practice a one‑minute explanation of the exchange argument on paper.
• Edge‑case drills: Include intervals with identical end times and zero‑length spans.
• Contrast exercises: Try sorting by start time to see why it fails; then repeat with end‑time sorting.
• Guided review: Tools like LeetCopilot can visualize overlaps and quickly show whether a skipped interval could have been swapped earlier.

Common Mistakes to Avoid

FAQ

How do I know greedy is allowed?
If you can define a locally optimal choice that doesn’t hurt future capacity and justify it with a swap argument, greedy is promising.

What should I study before this?
Review basic sorting stability and revisit the decision guide in How to Know When Dynamic Programming Is Needed to contrast with greedy.

Is the earliest‑finish rule unique?
For maximizing the count of intervals, yes; alternative orders risk blocking capacity.

How do I handle weighted intervals?
Weighted cases need DP; the simple greedy fails when intervals have different values.

Conclusion

Earliest‑finish greedy works because it locks in the smallest possible boundary each time, leaving maximal room for future picks. By rehearsing the swap argument, tracing examples, and keeping lastEnd as your invariant, you can explain and implement interval scheduling confidently in interviews.

If you’re looking for an AI assistant to help you master LeetCode patterns and prepare for interviews, check out LeetCopilot!

For coding interviews, check out LeetCopilot.