Interval Scheduling Greedy: Template, Proof, and All Variants

Interval scheduling is the most fundamental greedy pattern in algorithm interviews. It appears in dozens of LeetCode problems, from Meeting Rooms to Minimum Arrows to Burst Balloons.

But here's what makes it powerful: once you understand why sorting by end time works, you can solve an entire class of problems in minutes. The template is simple, the proof is elegant, and the pattern recognition is instant.

Yet most developers struggle with one question: "Why sort by end time instead of start time?" Understanding this distinction—and being able to prove it—is what separates those who memorize from those who master.

This comprehensive guide will teach you the complete interval scheduling template, rigorous proof of correctness, all variants, and common mistakes to avoid.

TL;DR

Use interval scheduling when:

• Maximizing/minimizing non-overlapping intervals
• Scheduling problems (meetings, activities, tasks)
• Need to select subset with no conflicts
• Can sort intervals

Template:

intervals.sort(key=lambda x: x[1])  # Sort by END time
count = 1
last_end = intervals[0][1]

for start, end in intervals[1:]:
    if start >= last_end:  # No overlap
        count += 1
        last_end = end

Time: O(n log n), Space: O(1)

Key insight: Sorting by end time (not start time) is provably optimal.

What Is Interval Scheduling?

The Classic Activity Selection Problem

Problem: Given n activities with start and end times, select the maximum number of non-overlapping activities.

Example:

Activities: [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11)]

Goal: Select maximum number with no time conflicts

Greedy solution:
  Sort by end time: [(1,4), (3,5), (5,7), (0,6), (3,9), (5,9), (6,10), (8,11)]
  
  Pick (1,4) - ends at 4
  Skip (3,5) - starts at 3 < 4 (overlaps)
  Pick (5,7) - starts at 5 ≥ 4 (no overlap)
  Skip (0,6), (3,9), (5,9), (6,10) - all overlap
  Pick (8,11) - starts at 8 ≥ 7 (no overlap)

Result: 3 activities [(1,4), (5,7), (8,11)] ✓

Why This Is Greedy (Not DP)

Greedy choice: Always pick the activity that ends earliest among remaining activities.

Why it works: Picking the earliest-ending activity leaves the maximum room for future activities. This greedy choice is provably optimal.

Contrast with DP: We don't need to explore all combinations. The greedy choice is guaranteed to be part of an optimal solution.

Time comparison:

• Brute force: O(2^n) - try all subsets
• DP: O(n²) - build up solutions
• Greedy: O(n log n) - sort + one pass

The Universal Template

Python Template

def interval_scheduling(intervals):
    """
    Template for interval scheduling (activity selection).
    
    Args:
        intervals: List of [start, end] pairs
    
    Returns:
        Maximum number of non-overlapping intervals
    
    Time: O(n log n)
    Space: O(1)
    """
    if not intervals:
        return 0
    
    # CRITICAL: Sort by END time (not start time)
    intervals.sort(key=lambda x: x[1])
    
    # Greedy selection
    count = 1
    last_end = intervals[0][1]
    
    for start, end in intervals[1:]:
        # Check if current interval overlaps with last selected
        if start >= last_end:
            # No overlap, select this interval
            count += 1
            last_end = end
    
    return count

# Example usage
intervals = [[1,4], [3,5], [0,6], [5,7]]
print(interval_scheduling(intervals))  # 2: [[1,4], [5,7]]

JavaScript Template

function intervalScheduling(intervals) {
    if (intervals.length === 0) return 0;
    
    // Sort by end time
    intervals.sort((a, b) => a[1] - b[1]);
    
    let count = 1;
    let lastEnd = intervals[0][1];
    
    for (let i = 1; i < intervals.length; i++) {
        const [start, end] = intervals[i];
        
        if (start >= lastEnd) {
            count++;
            lastEnd = end;
        }
    }
    
    return count;
}

// Example
const intervals = [[1,4], [3,5], [0,6], [5,7]];
console.log(intervalScheduling(intervals));  // 2

Java Template

public int intervalScheduling(int[][] intervals) {
    if (intervals.length == 0) return 0;
    
    // Sort by end time
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
    
    int count = 1;
    int lastEnd = intervals[0][1];
    
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= lastEnd) {
            count++;
            lastEnd = intervals[i][1];
        }
    }
    
    return count;
}

// Example
int[][] intervals = {{1,4}, {3,5}, {0,6}, {5,7}};
System.out.println(intervalScheduling(intervals));  // 2

Why Sort by End Time?

This is the most important question in interval scheduling. Understanding the answer separates memorization from mastery.

The Greedy Choice Property

Claim: Among all activities that are compatible with previously selected activities, the one with the earliest end time is always a safe choice.

Intuition: Selecting the earliest-ending activity leaves the maximum amount of time for future activities.

Visual proof:

Activities: [(1,4), (2,6), (5,8)]

Option 1: Pick (1,4) first
  Remaining time: [4, ∞)
  Can fit: (5,8) ✓
  Total: 2 activities

Option 2: Pick (2,6) first
  Remaining time: [6, ∞)
  Can fit: nothing ✗
  Total: 1 activity

Picking earliest-ending (1,4) is better ✓

Proof by Exchange Argument

Theorem: Greedy algorithm (sort by end time) produces an optimal solution.

Proof:

1. Let A = {a₁, a₂, ..., aₖ} be the greedy solution (sorted by end time)
2. Let O = {o₁, o₂, ..., oₘ} be an optimal solution (sorted by end time)
3. We'll show k = m (greedy is optimal)

Base case: If a₁ = o₁, both solutions start the same ✓

Exchange step: If a₁ ≠ o₁, then end(a₁) ≤ end(o₁) (by greedy choice)

• Replace o₁ with a₁ in O
• New solution O' is still valid because:
  • a₁ ends no later than o₁
  • All activities after o₁ in O are compatible with o₁
  • Therefore, they're also compatible with a₁ (ends earlier)
• O' has same size as O (still optimal)
• O' starts with a₁ (same as greedy)

Induction: Repeat for remaining activities

• Greedy and optimal solutions can be made identical
• Therefore, greedy is optimal ✓

Conclusion: Sorting by end time and greedily selecting is provably optimal.

Why Sorting by Start Time Fails

Counterexample:

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

Sort by START time: [(1,10), (2,3), (4,5)]
  Pick (1,10) - ends at 10
  Skip (2,3) - starts at 2 < 10 (overlaps)
  Skip (4,5) - starts at 4 < 10 (overlaps)
  Result: 1 activity ✗

Sort by END time: [(2,3), (4,5), (1,10)]
  Pick (2,3) - ends at 3
  Pick (4,5) - starts at 4 ≥ 3 (no overlap)
  Skip (1,10) - starts at 1 < 5 (overlaps)
  Result: 2 activities ✓

Sorting by start time gives suboptimal solution ✗

Why it fails: Picking earliest-starting activity might "block" many future activities if it runs long.

See detailed guide: Why Sort by End Time

Core Problems

1. Non-overlapping Intervals (LeetCode #435)

Problem: Given intervals, find minimum number to remove to make rest non-overlapping.

Solution:

def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    """
    Find minimum intervals to remove
    Time: O(n log n), Space: O(1)
    """
    if not intervals:
        return 0
    
    # Sort by end time
    intervals.sort(key=lambda x: x[1])
    
    # Count how many we can KEEP (greedy)
    keep = 1
    last_end = intervals[0][1]
    
    for start, end in intervals[1:]:
        if start >= last_end:
            keep += 1
            last_end = end
    
    # Remove = total - keep
    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]

Why it works: Maximum non-overlapping intervals = minimum to remove.

Edge case: Intervals touching at endpoints (e.g., [1,2] and [2,3]) are considered non-overlapping.

2. Minimum Number of Arrows (LeetCode #452)

Problem: Burst all balloons with minimum arrows (arrow at x bursts all balloons covering x).

Solution:

def findMinArrowShots(points: List[List[int]]) -> int:
    """
    Find minimum arrows to burst all balloons
    Time: O(n log n), Space: O(1)
    """
    if not points:
        return 0
    
    # Sort by end position
    points.sort(key=lambda x: x[1])
    
    arrows = 1
    arrow_pos = points[0][1]
    
    for start, end in points[1:]:
        # If balloon starts after arrow position, need new arrow
        if start > arrow_pos:
            arrows += 1
            arrow_pos = end
    
    return arrows

# Example
points = [[10,16], [2,8], [1,6], [7,12]]
print(findMinArrowShots(points))  # 2
# Arrow at 6: bursts [2,8] and [1,6]
# Arrow at 12: bursts [10,16] and [7,12]

Why it works: Shooting at earliest-ending balloon's end maximizes coverage.

Key difference from #435: Here we use > (strict) instead of >= because touching balloons can be burst by same arrow.

3. Meeting Rooms II (LeetCode #253)

Problem: Find minimum number of meeting rooms required.

Solution:

import heapq

def minMeetingRooms(intervals: List[List[int]]) -> int:
    """
    Find minimum meeting rooms needed
    Time: O(n log n), Space: O(n)
    """
    if not intervals:
        return 0
    
    # Sort by start time (different from activity selection!)
    intervals.sort(key=lambda x: x[0])
    
    # Min heap to track end times of ongoing meetings
    heap = []
    
    for start, end in intervals:
        # If earliest-ending meeting has ended, reuse room
        if heap and heap[0] <= start:
            heapq.heappop(heap)
        
        # Add current meeting's end time
        heapq.heappush(heap, end)
    
    # Heap size = number of rooms needed
    return len(heap)

# Example
intervals = [[0,30], [5,10], [15,20]]
print(minMeetingRooms(intervals))  # 2
# Room 1: [0,30]
# Room 2: [5,10], [15,20]

Why different: This asks for minimum resources (rooms), not maximum selection. We sort by start time and use a heap to track room availability.

Pattern recognition: "Minimum rooms/resources" → sort by start + heap, not greedy selection.

Variants

Variant 1: Weighted Intervals (When Greedy Fails)

Problem: Maximize total value of non-overlapping intervals (each has a weight).

Why greedy fails:

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

Greedy (end time): Pick (1,3), value=5
Optimal: Pick (2,4), value=10

Greedy fails ✗

Solution: Use DP, not greedy.

def weightedIntervalScheduling(intervals):
    """
    Maximize value of non-overlapping weighted intervals
    Time: O(n log n + n²), Space: O(n)
    """
    # Sort by end time
    intervals.sort(key=lambda x: x[1])
    n = len(intervals)
    
    # dp[i] = max value using intervals 0..i
    dp = [0] * n
    dp[0] = intervals[0][2]  # value
    
    for i in range(1, n):
        # Option 1: Don't take interval i
        exclude = dp[i-1]
        
        # Option 2: Take interval i
        include = intervals[i][2]
        
        # Find latest non-overlapping interval
        for j in range(i-1, -1, -1):
            if intervals[j][1] <= intervals[i][0]:
                include += dp[j]
                break
        
        dp[i] = max(exclude, include)
    
    return dp[n-1]

Key insight: Weights break greedy choice property. Need DP.

Variant 2: Interval Partitioning (Greedy Works)

Problem: Partition intervals into minimum number of groups such that no two intervals in same group overlap.

Solution: Same as Meeting Rooms II (sort by start + heap).

def intervalPartitioning(intervals):
    """
    Minimum groups for non-overlapping partition
    Time: O(n log n), Space: O(n)
    """
    intervals.sort(key=lambda x: x[0])
    heap = []
    
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)
        heapq.heappush(heap, end)
    
    return len(heap)

Why greedy works: We're not selecting a subset, we're partitioning all intervals. Greedy assignment to earliest-ending group is optimal.

Common Mistakes

Mistake 1: Sorting by Start Time

❌ Wrong:

intervals.sort(key=lambda x: x[0])  # WRONG for activity selection

✅ Correct:

intervals.sort(key=lambda x: x[1])  # Sort by END time

Why it matters: Counterexample: [(1,10), (2,3), (4,5)]

• Sort by start: picks (1,10), result=1 ✗
• Sort by end: picks (2,3), (4,5), result=2 ✓

See guide: Interval Scheduling Mistakes

Mistake 2: Off-by-One in Overlap Detection

❌ Wrong:

if start > last_end:  # Should be >=

✅ Correct:

if start >= last_end:  # Intervals touching at endpoints don't overlap

Why it matters:

• [1,2] and [2,3] are non-overlapping (touching is OK)
• Use >= for non-overlapping check
• Use > only if problem specifies strict non-overlap

Mistake 3: Not Handling Empty Input

❌ Wrong:

intervals.sort(key=lambda x: x[1])
last_end = intervals[0][1]  # Crashes if empty!

✅ Correct:

if not intervals:
    return 0

intervals.sort(key=lambda x: x[1])
last_end = intervals[0][1]

Mistake 4: Wrong Comparison Operator

❌ Wrong:

# For "Minimum Arrows" problem
if start >= arrow_pos:  # Should be >

✅ Correct:

if start > arrow_pos:  # Touching balloons can share arrow

Why it matters: Problem-specific. Read carefully whether touching counts as overlapping.

Complexity Analysis

Time Complexity:

• Sorting: O(n log n)
• One pass: O(n)
• Total: O(n log n)

Space Complexity:

• Sorting (in-place): O(1) or O(log n) for recursion
• No extra data structures: O(1)
• Total: O(1) (or O(log n) depending on sort implementation)

Comparison with alternatives:

When to Use Interval Scheduling

✅ Use When:

1. Maximizing non-overlapping intervals

   • "Maximum number of meetings"
   • "Maximum activities"

2. Minimizing removals

   • "Minimum intervals to remove"
   • "Minimum arrows to burst balloons"

3. Scheduling problems

   • "Activity selection"
   • "Job scheduling"

4. Intervals are unweighted

   • All intervals have equal value
   • Only care about count, not value

❌ Don't Use When:

1. Intervals have weights/values

   • Use DP instead
   • Greedy choice property fails

2. Need minimum resources

   • Use sort by start + heap
   • Different pattern (Meeting Rooms II)

3. Intervals can be reordered

   • Not an interval problem
   • Different pattern needed

Practice Problems

Master interval scheduling with these problems:

Beginner:

1. Non-overlapping Intervals (#435) - basic template
2. Minimum Arrows (#452) - slight variation
3. Meeting Rooms (#252) - check if possible

Intermediate:
4. Meeting Rooms II (#253) - minimum resources
5. Interval List Intersections (#986) - two sorted lists
6. Insert Interval (#57) - insertion into sorted

Advanced:
7. Merge Intervals (#56) - combine overlapping
8. Employee Free Time (#759) - multiple schedules
9. My Calendar I/II/III (#729, #731, #732) - booking system

FAQ

Q: Why sort by end time instead of start time?

A: Sorting by end time leaves maximum room for future intervals. Sorting by start time can pick a long interval that blocks many future ones. See Why Sort by End Time.

Q: What if intervals have equal end times?

A: Doesn't matter for correctness. Both will be considered, and the greedy algorithm will pick one. The result is still optimal.

Q: Do touching intervals overlap?

A: Depends on problem. Usually NO ([1,2] and [2,3] are non-overlapping). Use start >= last_end. Read problem carefully.

Q: Can I use this for weighted intervals?

A: No, greedy fails on weighted intervals. Use DP. See Greedy vs DP.

Q: What about Meeting Rooms II?

A: Different pattern (minimum resources, not maximum selection). Sort by start time + use heap. See problem #253 above.

Conclusion

Interval scheduling is the most fundamental greedy pattern, and mastering it unlocks dozens of LeetCode problems.

Key principles:

• Sort by END time (not start time)
• Greedy selection of earliest-ending interval
• Provably optimal via exchange argument
• O(n log n) time, O(1) space

The template:

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

When to use:

• Maximize non-overlapping intervals
• Minimize removals
• Unweighted scheduling

When NOT to use:

• Weighted intervals (use DP)
• Minimum resources (use heap)

Master this pattern, understand the proof, and you'll solve interval problems with confidence. For more patterns, see the complete greedy guide, Greedy vs DP, and Why Sort by End Time.

Next time you see "maximum non-overlapping intervals," reach for this template.