Greedy Algorithms: Core Patterns and Interval Scheduling

The Essence of Greedy

A Greedy Algorithm makes the locally optimal choice at each step, hoping that these local choices will lead to a global optimum.

It mirrors human intuition in everyday life: when organizing a drawer, you often place the largest items first to see what space remains. Greedy thinking is essentially about solving the most restrictive or largest part of the problem first, assuming the smaller parts will naturally fall into place.

Greedy vs. Dynamic Programming

Both rely on Optimal Substructure, but Greedy is a "one-way street":

The Greedy Choice Property is the linchpin: a local optimal choice does not destroy the potential for a global optimal solution. Proof typically involves the Exchange Argument: assuming an optimal solution exists that doesn't follow the greedy path, you show that swapping its choices for the greedy ones results in a solution that is at least as good.

Interval Scheduling: The Classic Pattern

Problem Statement

Given $N$ activities, each with a start and end time. You can only attend one activity at a time. What is the maximum number of activities you can participate in? (This is the dual of LeetCode 435).

Intuition: To maximize count, you must finish your current activity as soon as possible to leave the most room for the future. Sort by end time and greedily pick the earliest non-conflicting activity.

Non-overlapping Intervals (LeetCode 435)

Find the minimum number of intervals to remove to make the rest non-overlapping.

Reduction: Min removals = Total count - Max non-overlapping count.

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) return 0;
    // Sort by END time (right boundary)
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
    
    int kept = 0;          // Count of non-overlapping intervals kept
    int currentEnd = Integer.MIN_VALUE;
    
    for (int[] interval : intervals) {
        if (interval[0] >= currentEnd) { // Current interval starts after previous ends
            kept++;
            currentEnd = interval[1];
        }
        // Else: this interval overlaps; we skip it because it ends later 
        // than what we currently have (not contributing to the greedy goal)
    }
    return intervals.length - kept;
}

Merge Intervals (LeetCode 56)

Merge all overlapping intervals.

Strategy: Sort by the start time. This way, all potentially overlapping intervals are adjacent in the list.

public int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;
    
    // Sort by START time
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    
    List<int[]> result = new ArrayList<>();
    int[] current = intervals[0];
    
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= current[1]) {
            // Overlap detected: expand the current ending boundary
            current[1] = Math.max(current[1], intervals[i][1]);
        } else {
            // Gap detected: commit the current interval and start a new one
            result.add(current);
            current = intervals[i];
        }
    }
    result.add(current); // Commit the final interval
    return result.toArray(new int[result.size()][]);
}

Minimum Number of Arrows to Burst Balloons (LeetCode 452)

Balloons are represented as intervals along the X-axis. A single arrow at $x$ bursts all balloons covering that coordinate. Find the minimum arrows required.

Strategy: This is nearly identical to Interval Scheduling. You want to place an arrow at the rightmost possible point of a group of overlapping balloons to maximize its chance of hitting future balloons.

public int findMinArrowShots(int[][] points) {
    if (points.length == 0) return 0;
    // Sort by END time (right boundary)
    // Note: use Integer.compare to avoid overflow with subtraction
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    
    int arrows = 1;
    int arrowX = points[0][1]; // Place arrow at the end of the first balloon
    
    for (int i = 1; i < points.length; i++) {
        if (points[i][0] > arrowX) {
            // Current balloon starts after the arrow's position; need a new arrow
            arrows++;
            arrowX = points[i][1];
        }
        // Else: current balloon is already within the arrow's range
    }
    return arrows;
}

Technical Summary: Interval Greedy Logic

绝大多数区间贪心题都用交换论证法证明：

Key Takeaways

• Sort by End: Best for maximizing the count of items in a fixed space (leaving room for the remainder).
• Sort by Start: Best for merging contiguous ranges or coverage problems. 筋