贪心进阶：区间问题与跳跃变体

无重叠区间（LeetCode 435）

移除最少区间数，使剩余区间互不重叠（区间端点接触不算重叠）。

等价转化：最少移除数 = 总数 - 最多可保留的不重叠区间数。

贪心策略：按右端点升序排序，贪心选择结束最早的不重叠区间（给后续活动留出更多时间）。

int eraseOverlapIntervals(int[][] intervals) {
    // 按右端点升序排序
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    
    int count = 0;               // 可保留的不重叠区间数
    int end = Integer.MIN_VALUE; // 上一个保留区间的右端点

    for (int[] interval : intervals) {
        if (interval[0] >= end) {   // 左端点 >= 上一区间右端点 → 不重叠
            count++;
            end = interval[1];
        }
        // 否则跳过（与之前的区间重叠，移除代价更小）
    }
    return intervals.length - count;
}

模拟过程（[[1,2],[2,3],[3,4],[1,3]]，按右端点排序后 [1,2][2,3][1,3][3,4]）：

end = MIN_VALUE

[1,2]：1 >= MIN → 保留，end=2, count=1
[2,3]：2 >= 2  → 保留，end=3, count=2
[1,3]：1 < 3   → 重叠，跳过
[3,4]：3 >= 3  → 保留，end=4, count=3

最多保留 3 个 → 最少移除 4-3 = 1 个

注意：a[1] - b[1] 可能整数溢出，对于很大的值用 Integer.compare(a[1], b[1])。

跳跃游戏 II（LeetCode 45）

从 nums[0] 出发，每步最多跳 nums[i] 格，保证到达末尾，求最少跳跃次数。

贪心分层：把所有从同一次跳跃能到达的位置分为一层。每次必须跳时（到达当前层的边界），选能到最远的那一跳。

int jump(int[] nums) {
    int jumps = 0;    // 跳跃次数
    int curEnd = 0;   // 当前层的右边界
    int farthest = 0; // 下一层能到的最远位置

    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == curEnd) {      // 到达当前层边界，必须起跳
            jumps++;
            curEnd = farthest;  // 推进到下一层
        }
    }
    return jumps;
}

图示（nums = [2,3,1,1,4]）：

位置：  0   1   2   3   4
跳力：  2   3   1   1   4

第0跳（出发点）：覆盖 [0,2]
第1跳：从[0,2]中最远能到3·4=4 → 覆盖 [1,4]
       到位置4，结束

共跳 2 次 ✓

跳跃游戏 III（LeetCode 1306）

从 start 出发，每步可以跳 +arr[i] 或 -arr[i]（不越界），能否到达任意值为 0 的位置。

这道题不是贪心，是 BFS：在图中搜索能到达 0 的节点。

boolean canReach(int[] arr, int start) {
    int n = arr.length;
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);

    while (!queue.isEmpty()) {
        int i = queue.poll();
        if (arr[i] == 0) return true;   // 找到目标
        if (visited[i]) continue;
        visited[i] = true;

        int right = i + arr[i];
        int left = i - arr[i];
        if (right < n) queue.offer(right);
        if (left >= 0) queue.offer(left);
    }
    return false;
}

复杂度：O(n) 时间，O(n) 空间。

跳跃游戏 VI（LeetCode 1696）

从起点出发，每次跳 1～k 步，累计最大分数（dp + 单调队列）。

虽然名字叫跳跃游戏，但本质是 DP + 单调队列优化：dp[i] = max(dp[i-k..i-1]) + nums[i]。

单调队列维护滑动窗口最大值：

int maxResult(int[] nums, int k) {
    int n = nums.length;
    int[] dp = new int[n];
    dp[0] = nums[0];

    // 单调递减队列（存下标），队头是窗口内 dp 最大的下标
    Deque<Integer> deque = new ArrayDeque<>();
    deque.offerLast(0);

    for (int i = 1; i < n; i++) {
        // 移除超出窗口的元素（窗口大小 k）
        while (deque.peekFirst() < i - k) deque.pollFirst();

        // 队头是 [i-k, i-1] 内 dp 最大的下标
        dp[i] = dp[deque.peekFirst()] + nums[i];

        // 维护单调递减（弹出队尾中 dp 值更小的）
        while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i])
            deque.pollLast();
        deque.offerLast(i);
    }
    return dp[n - 1];
}

模拟过程（nums=[1,-1,-2,4,-7,3], k=2）：

dp[0]=1, deque=[0]

i=1: 窗口[0,1], 队头dp=1, dp[1]=1+(-1)=0
     dp[1]<dp[0], deque=[0,1]

i=2: 窗口[1,2], 队头(0<1?) 0不在窗口 → 弹0; 队头=1, dp[2]=0+(-2)=-2
     dp[2]<dp[1], deque=[1,2]

i=3: 窗口[2,3], 队头=1 (1<3-2=1? 不行,1=1不弹出); 
     实际 i-k=1, deque.peek=1 < 1? 不成立→不弹
     dp[3]=dp[1]+4=0+4=4
     4>-2: 弹2; 4>0: 弹1; deque=[3]

...结果 dp[5]=3 ✓

会议室 II（经典题）

给定 n 个会议区间，求同时需要多少间会议室（并发最大数）。

贪心：分别按开始和结束时间排序，模拟会议室的分配：

int minMeetingRooms(int[][] intervals) {
    int n = intervals.length;
    int[] start = new int[n], end = new int[n];
    for (int i = 0; i < n; i++) {
        start[i] = intervals[i][0];
        end[i] = intervals[i][1];
    }
    Arrays.sort(start);
    Arrays.sort(end);

    int rooms = 0, endPtr = 0;
    for (int s : start) {
        if (s < end[endPtr]) {
            rooms++;          // 会议开始时还有会议在进行，需新房间
        } else {
            endPtr++;         // 一个会议结束，房间可复用
        }
    }
    return rooms;
}

总结

贪心与 DP 的边界：当"选最优"的决策不依赖于后续状态时，用贪心；当最优决策需要"试所有可能"时，用 DP。单调队列往往是两者的桥梁。