Advanced Greedy: Complex Intervals and Jump Variants

Non-overlapping Intervals (LeetCode 435)

Remove the minimum number of intervals to make the rest non-overlapping (touching at endpoints is fine).

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

Greedy Logic: Sort by end times. Selecting the interval that finishes earliest provides the maximum possible space for subsequent intervals.

public int eraseOverlapIntervals(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 = 0;              // Non-overlapping count
    int currentEnd = Integer.MIN_VALUE;

    for (int[] interval : intervals) {
        if (interval[0] >= currentEnd) {
            count++;
            currentEnd = interval[1];
        }
    }
    return intervals.length - count;
}

Jump Game II (LeetCode 45) - Layered Greedy

Find the minimum number of jumps to reach the end.

Logic: Visualize the jumps as layers. Every location you can reach within $N$ jumps belongs to layer $N$. When you hit the boundary of the current layer, you must perform another jump to enter the next layer, extending your reach to the furthest possible point available in the current layer.

public int jump(int[] nums) {
    int jumps = 0, currentBoundary = 0, farthestReach = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        farthestReach = Math.max(farthestReach, i + nums[i]);
        if (i == currentBoundary) {
            jumps++;
            currentBoundary = farthestReach;
        }
    }
    return jumps;
}

Jump Game VI (LeetCode 1696) - DP + Monotonic Queue

Jump $1$ to $k$ steps to maximize total score.

The Hybrid Approach: This is technically DP optimized by a Monotonic Queue. The state transition is dp[i] = max(dp[i-k...i-1]) + nums[i]. A monotonic queue allows us to find the maximum in the $k$-window in $O(1)$ time.

public int maxResult(int[] nums, int k) {
    int n = nums.length;
    int[] dp = new int[n];
    dp[0] = nums[0];
    
    // Monotonic DECREASING queue to store indices of DP values
    Deque<Integer> deque = new ArrayDeque<>();
    deque.offerLast(0);
    
    for (int i = 1; i < n; i++) {
        // 1. Remove indices that are outside the k-window
        if (deque.peekFirst() < i - k) deque.pollFirst();
        
        // 2. The front of the queue has the max DP value from the window
        dp[i] = nums[i] + dp[deque.peekFirst()];
        
        // 3. Maintain monotonicity: remove elements smaller than current dp[i]
        while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
    }
    return dp[n - 1];
}

Meeting Rooms II (Classic Design)

Given $N$ meeting intervals, find the minimum number of rooms required.

Greedy Strategy: Treat meeting starts and ends as independent events. Sort the start times and end times separately.

public int minMeetingRooms(int[][] intervals) {
    int n = intervals.length;
    int[] starts = new int[n];
    int[] ends = new int[n];
    for (int i = 0; i < n; i++) {
        starts[i] = intervals[i][0];
        ends[i] = intervals[i][1];
    }
    Arrays.sort(starts);
    Arrays.sort(ends);
    
    int rooms = 0, endPtr = 0;
    for (int i = 0; i < n; i++) {
        if (starts[i] < ends[endPtr]) {
            // A new meeting starts before an old one ends: we need a new room
            rooms++;
        } else {
            // An old meeting ends: we can reuse its room
            endPtr++;
        }
    }
    return rooms;
}

Comparative Matrix

[!TIP] Greedy vs. DP: Use Greedy when the "locally best" choice does not invalidate future results. Use DP (often with monotonic optimization) when "the best" depends on previous states that must be evaluated systematically. 筋