Greedy Interval Scheduling Intuition with Proofs

Interval scheduling looks simple—pick non-overlapping intervals and maximize selections—but interviewers often ask why the greedy works. This guide builds intuition for the earliest-finish strategy, provides a simple correctness sketch, and shows how to narrate it confidently.

TL;DR

• Topic: selecting the maximum number of non-overlapping intervals using the earliest finish time greedy.
• Why it matters: interviews test whether you can justify the greedy choice, not just output a sorted loop.
• Core steps: sort by end time, iterate once, keep intervals that start after the last chosen end.
• Common confusion: mixing start-time sorting 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. Choosing the earliest end time leaves 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. This aligns with the counterexample habits in 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
Skip [2,3] (touches boundary? allow if >=) → pick, 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):
    intervals.sort(key=lambda x: x[1])
    chosen = []
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen

The code tracks one 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.
• Use guided review: Tools like LeetCopilot can visualize overlaps and quickly show whether a skipped interval could have been swapped earlier.

Common Mistakes to Avoid

Sorting by start time

This can miss optimal sets when an early-start interval ends late, blocking future picks.

Allowing overlaps accidentally

Forgetting the start >= lastEnd check selects incompatible intervals and breaks maximality.

Misreading equal boundaries

Decide whether touching intervals (end == start) are allowed; most interview variants allow them.

Over-explaining code, under-explaining proof

Interviewers often care more about why the greedy is safe than the loop itself.

FAQ

• How do I know greedy is allowed? If you can define a locally optimal choice that doesn’t hurt future capacity and can 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 maximal interval counts, yes; alternative orders risk blocking capacity.
• How do I handle weighted intervals? Weighted cases need DP; the simple greedy fails without weights being uniform.

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.