GU𝐆𝐫𝐨𝐰 𝐔𝐩
返回文章列表
数据结构与算法
算法贪心区间

区间调度：重叠区间问题全家桶

区间题三板斧

LeetCode 上有一族题，输入都是一串区间，输出是"删几个、合几段、切几刀"。它们共享同一套解题骨架，我称之为三板斧：

  1. 排序：把区间按左端点或右端点排好，让"重叠"变成相邻区间之间的局部关系；
  2. 遍历比较：线性扫描，只看"当前区间"和"上一个区间"的关系，维护一个边界值；
  3. 决策：按题意做三选一——合并（扩展结果集）、删除（计数器 +1）、切分（边界处结算）。

排序是这套打法的灵魂。排序之后，"任意两个区间是否重叠"这个全局问题，塌缩成"相邻两个区间是否重叠"这个局部问题——这正是贪心擅长的场景：局部比较 + 不回头推进。

排序键选左端点还是右端点？没有统一答案，取决于题目要"保住什么"。下面三道题会给出三种不同的答案。

无重叠区间（435）：按右端点排序

435. 无重叠区间：给定若干区间，求移除的最小区间数，使剩余区间互不重叠。

反着想更好做：移除最少 = 保留最多。要保留尽可能多的互不重叠区间，每次都应该"尽早结束当前区间"，给后面留出最大空间——所以按右端点排序，右端点小的优先保留。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 按右端点升序：右端点越小，占用的"地盘"越少，越值得保留
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
 
        int keep = 1;                     // 至少保留第一个区间
        int end = intervals[0][1];        // 当前已保留区间的右边界
 
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= end) {
                // 不重叠：这个区间可以保留
                keep++;
                end = intervals[i][1];
            } else {
                // 重叠：必须移除一个。贪心已保证保留的是右端点更小的，
                // 所以只更新计数，end 不变
            }
        }
        return intervals.length - keep;
    }
}

论证一下正确性：排序后第一个区间右端点全局最小，保留它绝不吃亏（任何其他选择留下的空间都不比它大）；后续同理，每次遇到重叠，被移除的一定是"右端点更靠后"的那个。这其实就是经典的区间调度（活动选择）问题。

两个实现细节：

  1. 边界判断：end == intervals[i][0] 时区间相接不算重叠（>=），如果题目把相接也算重叠，改成 > 即可；
  2. Comparator 别用减法：a[1] - b[1] 在端点一正一负且绝对值很大时会整型溢出，Integer.compare 是安全写法。

合并区间（56）：原地扩展结果集

56. 合并区间：把所有重叠的区间合并成一个，返回不重叠的区间列表（按左端点有序）。

这次目标变成"合并"而不是"删除"，排序键换成左端点：排序后所有"可以被合并"的区间一定是连续的一段。维护结果集最后一个区间，能扩就扩，不能扩就入列。

class Solution {
    public int[][] merge(int[][] intervals) {
        // 按左端点升序：重叠/可合并的区间会排在一起
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
 
        List<int[]> merged = new ArrayList<>();
        merged.add(intervals[0]); // 第一个区间直接入列
 
        for (int i = 1; i < intervals.length; i++) {
            int[] last = merged.get(merged.size() - 1); // 结果集最后一个区间
            if (intervals[i][0] <= last[1]) {
                // 重叠：扩展最后一个区间的右端点（取两者较大值）
                // 注意必须是 max，因为前一个右端点可能更长
                last[1] = Math.max(last[1], intervals[i][1]);
            } else {
                // 不重叠：作为新区间入列
                merged.add(intervals[i]);
            }
        }
        return merged.toArray(new int[0][]);
    }
}

这题有个高频易错点：扩展右端点必须 Math.max(last[1], intervals[i][1])，不能直接赋值。反例：[1,10] 和 [2,3]，排序后依次处理，若直接赋值会把右端点从 10 缩成 3，与后面 [5,8] 的合并就错了。

对比 435 和 56 的手感差异：435 排右端点、只需要一个标量 end 记边界；56 排左端点、需要维护"最后一个区间"并可能修改它。为什么 56 不能排右端点？ 因为合并后的新区间右端点会变长，右端点排序无法保证"当前处理的区间右端点最大"，扩展逻辑会乱；而左端点排序天然有序，只改右端点不影响遍历顺序。

划分字母区间（763）：记录最后出现位置

763. 划分字母区间：把字符串切成尽可能多的段，使每个字母只出现在一个段里，返回每段长度。

这题表面上没有区间输入，但每个字母"从首次出现到末次出现"天然构成一个区间，切段就是把这些重叠区间分桶。做法分两步：

  1. 预处理：记录每个字母最后出现的下标；
  2. 扫描：维护当前段的"最远边界"，边界追上扫描位置时，说明这段内所有字母都不会再出现了——切一刀。
class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        // 第一步：记录每个字母最后出现的位置
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }
 
        List<Integer> result = new ArrayList<>();
        int start = 0;   // 当前段的起点
        int end = 0;     // 当前段必须覆盖到的最远位置
 
        for (int i = 0; i < s.length(); i++) {
            // 第二步：段边界贪心扩展为当前字母的末次出现位置
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                // 扫描位置追上边界：段内字母都不会再出现，切一刀
                result.add(i - start + 1);
                start = i + 1;
            }
        }
        return result;
    }
}

用 "ababcbaca..." 的开头演示一下边界推进：

下标:  0 1 2 3 4 5 6 7 8
字符:  a b a b c b a c a
last:  a→8  b→5  c→7
 
i=0: end = max(0, last[a]=8) → 8
i=1: end = max(8, last[b]=5) → 8
...一路推进...
i=8: i == end(8)，切出第一段长度 9

为什么贪心正确？段的边界只会被"段内字母的末次出现"撑大，而末次出现位置是客观事实、与怎么切无关；i == end 时切刀既不早（段内字母还没用完）也不晚（再晚只是白白加长当前段、减少段数）。

排序策略对比表

三道题（加上变式）的排序/预处理策略放在一起看：

题目 预处理 排序/扫描键 维护的量 相接算重叠吗
435 无重叠区间 按右端点排序 右端点 end 保留计数 不算（>=）
56 合并区间 按左端点排序 左端点 结果集末区间（可修改） 算（<= 即合并）
763 划分字母区间 last[] 数组 下标顺序扫描 段的最远边界 —
452 射气球（变式） 按右端点排序 右端点 当前"一支箭"的位置 算触碰（<= 即同箭）

规律总结：要"保留/计数"就排右端点（尽早结束给后面腾地方）；要"合并/扩展"就排左端点（保证合并对象连续）。记住这句，区间组的大部分题都能秒出排序策略。

复杂度与易错点

  • 复杂度：三题统一为时间 O(n log n)（排序主导），空间 O(log n)（排序栈深；56 的结果集不计入，763 的 last 数组是 O(26)）。
  • 易错点：
    1. Comparator 用减法：端点差值溢出，一律 Integer.compare；
    2. 56 直接赋值右端点：必须 Math.max，否则短区间会把长区间的右边界缩坏；
    3. 435 的 end 忘记更新或不该更新：保留时更新 end，移除时不更新（移除的是右端点更大的那个）；
    4. 763 忘记 i == end 用 == 而写成 >=：逻辑上等价，但写 == 更能表达"恰好追上"的语义，也更容易发现边界 bug；
    5. 对"相接"语义不敏感：435 中 [1,2] 与 [2,3] 不重叠，56 中却要合并，两题相反，读题时先确认。

LeetCode 题目清单

参考