Interval Scheduling: Why Sort by End Time Works (Proof and Intuition)

You're solving an interval scheduling problem. You know you need to sort, but which key do you sort by?

Start time? End time? Duration? The choice seems arbitrary, but it's actually the most critical decision in interval scheduling.

Sort by start time: Suboptimal, fails on simple examples.
Sort by end time: Provably optimal, works every time. ✓

But why? Understanding this distinction—and being able to prove it—is what separates those who memorize from those who master greedy algorithms.

TL;DR

Sort by END time for interval scheduling because:

• ✅ Leaves maximum room for future intervals
• ✅ Provably optimal via exchange argument
• ✅ Greedy choice property holds

Don't sort by START time because:

• ❌ Can pick long interval that blocks many future intervals
• ❌ Suboptimal (counterexample exists)
• ❌ Greedy choice property fails

The intuition: Finishing early leaves more time for future activities.

The Intuition: Leave Room for Future Activities

Visual Example

Problem: Select maximum non-overlapping intervals.

Intervals: [(1,10), (2,3), (4,5)]

Sort by START time:

Sorted: [(1,10), (2,3), (4,5)]

Pick (1,10) - starts earliest
  Ends at 10
  
Check (2,3):
  Starts at 2 < 10 → OVERLAPS, skip
  
Check (4,5):
  Starts at 4 < 10 → OVERLAPS, skip

Result: 1 interval ✗

Sort by END time:

Sorted: [(2,3), (4,5), (1,10)]

Pick (2,3) - ends earliest
  Ends at 3
  
Check (4,5):
  Starts at 4 ≥ 3 → NO OVERLAP, pick
  Ends at 5
  
Check (1,10):
  Starts at 1 < 5 → OVERLAPS, skip

Result: 2 intervals ✓ (optimal)

The key insight: Interval (1,10) starts early but runs long, blocking (2,3) and (4,5). Picking (2,3) first (ends earliest) leaves room for (4,5).

The Greedy Choice

Greedy choice: Among all remaining intervals, pick the one that ends earliest.

Why it's optimal: Ending early leaves the maximum amount of time for future intervals.

Analogy: You're scheduling meetings in a conference room. To fit the most meetings, always pick the one that frees up the room earliest, giving you the most time for future meetings.

The Formal Proof (Exchange Argument)

Theorem

Claim: Greedy algorithm (sort by end time, pick earliest-ending) produces an optimal solution.

Proof by Exchange Argument:

Let:

• G = {g₁, g₂, ..., gₖ} be the greedy solution (sorted by end time)
• O = {o₁, o₂, ..., oₘ} be an optimal solution (sorted by end time)

We'll show k = m (greedy is optimal).

Step 1: Base Case

If g₁ = o₁, both solutions start the same. ✓

Step 2: Exchange

If g₁ ≠ o₁, then end(g₁) ≤ end(o₁) (by greedy choice of earliest end).

Replace o₁ with g₁ in O to get O':

• O' = {g₁, o₂, ..., oₘ}

Claim: O' is still a valid solution.

Proof:

• g₁ ends no later than o₁: end(g₁) ≤ end(o₁)
• All intervals after o₁ in O are compatible with o₁
• Since g₁ ends earlier, they're also compatible with g₁
• Therefore, O' is valid ✓

Step 3: Size Preservation

• |O'| = |O| = m (same number of intervals)
• O is optimal, so O' is also optimal
• O' starts with g₁ (same as greedy)

Step 4: Induction

Repeat for remaining intervals:

• Greedy picks g₂ (earliest-ending among remaining)
• O' has some interval o₂' after g₁
• Exchange o₂' with g₂ (same argument)
• Continue until all intervals matched

Conclusion: Greedy solution can be transformed into optimal solution without changing size. Therefore, greedy is optimal. ✓

Visual Proof

Optimal solution O:
  [----o₁----]     [--o₂--]  [--o₃--]
       ↓ exchange
  [--g₁--]         [--o₂--]  [--o₃--]
  
g₁ ends earlier than o₁, so no new conflicts.
O' is still optimal, now starts with greedy choice.

Repeat for o₂, o₃, ... → entire solution becomes greedy.
Therefore, greedy is optimal. ✓

Why Sorting by Start Time Fails

The Counterexample

Intervals: [(1,10), (2,3), (4,5), (6,7), (8,9)]

Sort by START time:

Sorted: [(1,10), (2,3), (4,5), (6,7), (8,9)]

Greedy picks (1,10) - starts earliest
  All other intervals overlap with (1,10)
  
Result: 1 interval ✗

Sort by END time:

Sorted: [(2,3), (4,5), (6,7), (8,9), (1,10)]

Greedy picks:
  (2,3) - ends at 3
  (4,5) - starts at 4 ≥ 3, ends at 5
  (6,7) - starts at 6 ≥ 5, ends at 7
  (8,9) - starts at 8 ≥ 7, ends at 9
  
Result: 4 intervals ✓ (optimal)

The problem: Sorting by start time can pick a long interval that blocks many short intervals.

Why Greedy Choice Property Fails

Greedy choice (start time): "Pick interval that starts earliest."

Counterexample:

Intervals: [(1,10), (2,3)]

Greedy picks (1,10) - starts earliest
  Result: 1 interval
  
Optimal: Pick (2,3)
  Result: 1 interval (same)
  
But add more intervals: [(1,10), (2,3), (4,5)]

Greedy picks (1,10)
  Result: 1 interval ✗
  
Optimal: Pick (2,3), (4,5)
  Result: 2 intervals ✓

Conclusion: Greedy choice property doesn't hold for start time. Picking earliest-starting interval is not always part of an optimal solution.

Why Sorting by Duration Fails

Greedy choice (duration): "Pick shortest interval first."

Counterexample:

Intervals: [(1,2), (3,10), (4,5), (6,7), (8,9)]

Sort by duration: [(1,2), (4,5), (6,7), (8,9), (3,10)]

Greedy picks:
  (1,2) - duration 1
  (4,5) - starts at 4 ≥ 2, duration 1
  (6,7) - starts at 6 ≥ 5, duration 1
  (8,9) - starts at 8 ≥ 7, duration 1
  
Result: 4 intervals

But optimal might be different depending on overlaps.

The problem: Duration doesn't account for when intervals occur. Two short intervals might overlap, while a long interval might not.

Code Comparison

❌ Wrong: Sort by Start Time

def maxIntervals(intervals):
    # WRONG: Sort by start time
    intervals.sort(key=lambda x: x[0])
    
    count = 1
    last_end = intervals[0][1]
    
    for start, end in intervals[1:]:
        if start >= last_end:
            count += 1
            last_end = end
    
    return count

# Counterexample
intervals = [[1,10], [2,3], [4,5]]
print(maxIntervals(intervals))  # 1 (WRONG, optimal is 2)

✅ Correct: Sort by End Time

def maxIntervals(intervals):
    # CORRECT: Sort by end time
    intervals.sort(key=lambda x: x[1])
    
    count = 1
    last_end = intervals[0][1]
    
    for start, end in intervals[1:]:
        if start >= last_end:
            count += 1
            last_end = end
    
    return count

# Same example
intervals = [[1,10], [2,3], [4,5]]
print(maxIntervals(intervals))  # 2 (CORRECT)

Real LeetCode Problems

Non-overlapping Intervals (#435)

Problem: Minimum intervals to remove to make rest non-overlapping.

Solution: Sort by end time, count maximum non-overlapping.

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[1])  # Sort by END time
    
    keep = 1
    last_end = intervals[0][1]
    
    for start, end in intervals[1:]:
        if start >= last_end:
            keep += 1
            last_end = end
    
    return len(intervals) - keep

# Example
intervals = [[1,2], [2,3], [3,4], [1,3]]
print(eraseOverlapIntervals(intervals))  # 1
# Keep [1,2], [2,3], [3,4], remove [1,3]

Minimum Arrows (#452)

Problem: Minimum arrows to burst all balloons.

Solution: Sort by end position, shoot at earliest-ending balloon.

def findMinArrowShots(points):
    points.sort(key=lambda x: x[1])  # Sort by END position
    
    arrows = 1
    arrow_pos = points[0][1]
    
    for start, end in points[1:]:
        if start > arrow_pos:  # Note: > not >=
            arrows += 1
            arrow_pos = end
    
    return arrows

# Example
points = [[10,16], [2,8], [1,6], [7,12]]
print(findMinArrowShots(points))  # 2

Common Mistakes

Mistake 1: Sorting by Start Time

❌ Wrong:

intervals.sort(key=lambda x: x[0])  # Start time

✅ Correct:

intervals.sort(key=lambda x: x[1])  # End time

Mistake 2: Sorting by Duration

❌ Wrong:

intervals.sort(key=lambda x: x[1] - x[0])  # Duration

✅ Correct:

intervals.sort(key=lambda x: x[1])  # End time

Mistake 3: Not Understanding Why

❌ Wrong:

# "I'll just memorize: sort by end time"
# (doesn't understand why)

✅ Correct:

# "Sort by end time because it leaves maximum room for future intervals"
# (understands the greedy choice property)

Quick Reference

Practice Strategy

To master this concept:

1. Solve Non-overlapping Intervals (#435) with end time sorting
2. Try start time sorting and see it fail
3. Understand the counterexample [(1,10), (2,3), (4,5)]
4. Prove correctness using exchange argument
5. Solve Minimum Arrows (#452) to reinforce

FAQ

Q: Why does sorting by end time work?

A: It leaves the maximum amount of time for future intervals. Provably optimal via exchange argument.

Q: Can I ever sort by start time?

A: For interval scheduling (maximum selection), no. For other problems (like Meeting Rooms II), yes.

Q: What if intervals have equal end times?

A: Doesn't matter for correctness. Both will be considered, greedy will pick one.

Q: How do I remember this?

A: Think: "Finish early to leave room for more." End time determines when room is free.

Conclusion

Sorting by end time is the most important greedy insight for interval scheduling.

Key takeaways:

• Sort by END time for maximum non-overlapping intervals
• Leaves maximum room for future intervals
• Provably optimal via exchange argument
• Don't sort by start time (counterexample exists)

The intuition:

• Finishing early → more time for future activities
• Like scheduling meetings: free up the room ASAP

The proof:

• Exchange argument shows greedy equals optimal
• Earliest-ending interval is always a safe choice

Master this insight, and you'll solve all interval scheduling problems with confidence. For more patterns, see Interval Scheduling Template and the complete greedy guide.

Next time you see "maximum non-overlapping intervals," sort by end time.