罗罗编程学习记录
本页内容 展开查看

02.8.1.2 区间与调度贪心

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.8 贪心与技巧题 / 02.8.1 贪心与技巧

02.8.1.2-001 最多不重叠区间怎么选?

一句话结论

按结束时间升序,依次选与已选区间不冲突的区间;结束最早者给后续留最多空间,得到最多不重叠区间数。

概念解释

  • 冲突:两区间有公共点。
  • 兼容:后一开始不早于前一结束。
  • 目标:区间数量最大。

原理流程

  1. 按右端点升序排序。
  2. end 记录已选最右边界。
  3. 当前左端点 >= end 则选中并更新 end。

代码 / 示例

int maxNonOverlap(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
    int count = 0, end = Integer.MIN_VALUE;
    for (int[] it : intervals) {
        if (it[0] >= end) { count++; end = it[1]; }
    }
    return count;
}

常见误区

  • 误区:按开始时间最早选;正解:跨度大的早开始区间会挤占后续空间。
  • 误区:端点相接算重叠;正解:按题意,通常 start >= end 即兼容。

追问

  • Q:复杂度? A:排序 O(n log n),扫描 O(n),空间 O(1)(不计排序栈)。
  • Q:最少移除多少区间? A:总数 - 最多不重叠数。

02.8.1.2-002 合并重叠区间怎么做?

一句话结论

按开始时间升序,维护当前合并区间的右边界;下一区间开始不超过右边界则合并并扩展右边界,否则封存当前区间开启新区间。

概念解释

  • 开始排序:保证左侧已处理,只需比较右端。
  • 右边界扩展:取两者右端较大值。
  • 目标:输出互不重叠的合并结果。

原理流程

  1. 按左端点升序。
  2. 结果集空则压入首区间。
  3. 比较当前区间与结果末区间右端,重叠则合并,否则追加。

代码 / 示例

int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    List<int[]> res = new ArrayList<>();
    for (int[] it : intervals) {
        if (res.isEmpty() || res.get(res.size()-1)[1] < it[0]) res.add(it);
        else res.get(res.size()-1)[1] = Math.max(res.get(res.size()-1)[1], it[1]);
    }
    return res.toArray(new int[0][]);
}

常见误区

  • 误区:合并时右端取较小值;正解:要覆盖全部重叠部分,取较大右端。
  • 误区:未排序直接合并;正解:乱序下相邻比较会漏掉跨区间重叠。

追问

  • Q:端点相接是否合并? A:按题意,重叠含端点时合并,相接不算重叠时不合并。
  • Q:复杂度? A:O(n log n) 时间,O(n) 结果空间。

02.8.1.2-003 向有序区间集插入新区间并合并怎么做?

一句话结论

先加入所有结束早于新区间开始的区间,再合并所有与新区间重叠的区间(更新左右边界),最后追加剩余区间;无需重排,一次线性扫描。

概念解释

  • 前段:不重叠且在左侧。
  • 中段:与新区间相交,合并边界。
  • 后段:在右侧不重叠。

原理流程

  1. 复制输入并加入新区间,或分段扫描原有序数组。
  2. 前段追加 → 中段合并 → 后段追加。
  3. 输出合并结果。

代码 / 示例

left = newL, right = newR;遍历:end < left 追加;start <= right 则 right=max;否则先压入合并区间

常见误区

  • 误区:把新区间直接排序插入再合并;正解:原数组已有序,可线性分段,更省。
  • 误区:中段合并时漏更新左边界;正解:左边界取最小开始,右边界取最大结束。

追问

  • Q:新区间完全被包含怎么办? A:中段合并后边界不变,等价于被吸收。
  • Q:复杂度? A:O(n) 时间,O(n) 结果空间。

02.8.1.2-004 用最少箭引爆气球(LC 452 类)怎么贪?

一句话结论

按右端点升序,一支箭打在当前区间右端;后续区间开始不超过该右端则被同支覆盖,否则开新箭;与区间调度同构,目标是最少箭数。

概念解释

  • 一箭覆盖一批右端相接/包含的区间。
  • 右端排序:最早结束处放箭,覆盖后续尽可能多气球。
  • 目标:箭数最少。

原理流程

  1. 按右端升序。
  2. 首箭定在首区间右端。
  3. 后续开始 > 当前箭位则新增箭并更新位置。

代码 / 示例

int findMinArrowShots(int[][] points) {
    Arrays.sort(points, Comparator.comparingInt(a -> a[1]));
    int arrows = 1, pos = points[0][1];
    for (int[] p : points) {
        if (p[0] > pos) { arrows++; pos = p[1]; }
    }
    return arrows;
}

常见误区

  • 误区:按左端点排序放箭;正解:右端点决定一箭最远覆盖位置。
  • 误区:端点相等不算覆盖;正解:气球区间含端点,start <= pos 即被引爆。

追问

  • Q:与最多不重叠区间什么关系? A:互为补集视角,排序键相同,计数口径不同。
  • Q:复杂度? A:O(n log n) 时间,O(1) 空间。

02.8.1.2-005 会议室数量(最大同时开会区间)怎么求?

一句话结论

求区间最大重叠数:按开始事件与结束事件排序扫描,开始 +1、结束 -1,过程峰值即所需会议室数;或用最小堆维护正在进行的会议结束时间。

概念解释

  • 重叠深度:同一时刻并行会议数。
  • 事件扫描:开始计数加,结束计数减。
  • 堆法:结束最早者先释放会议室。

原理流程

  1. 事件排序:先结束后开始(端点相等时)。
  2. 扫描累加计数,记录峰值。
  3. 输出峰值。

代码 / 示例

// 堆法:按开始排序,堆顶结束早;开始 >= 堆顶则弹出复用,否则会议室 +1

常见误区

  • 误区:开始与结束同时发生时先加后减;正解:会议结束即释放,应先 -1,避免高估房间数。
  • 误区:会议室数等于区间总数;正解:只算并行峰值。

追问

  • Q:事件扫描复杂度? A:O(n log n) 排序,O(n) 扫描。
  • Q:堆法复杂度? A:O(n log n),堆大小为并行会议数。

02.8.1.2-006 最少区间覆盖整条目标区间怎么选?

一句话结论

在当前覆盖右边界内,选开始不超过当前边界且右端最远的区间,扩展覆盖;每次选跨度贡献最大者,直到覆盖目标左端到右端。

概念解释

  • 当前边界:已覆盖到的最右位置。
  • 候选:开始 <= 当前边界的区间。
  • 扩展目标:右端尽可能远。

原理流程

  1. 按开始排序。
  2. 每轮在候选内取右端最远,更新边界。
  3. 边界未推进则无法覆盖,返回失败。

代码 / 示例

curEnd 内扫描所有 start <= curEnd 的区间,nextEnd = max(right);curEnd = nextEnd

常见误区

  • 误区:按区间长度排序选最短;正解:目标是覆盖连续段,选能把右边界推最远者。
  • 误区:一轮扫描只比较相邻区间;正解:要在整个候选集内取最大右端。

追问

  • Q:无法覆盖怎么判定? A:下一轮 nextEnd 不大于 curEnd,存在缺口。
  • Q:复杂度? A:排序 O(n log n),扫描 O(n)。

02.8.1.2-007 区间交集怎么求?

一句话结论

两组区间各自有序,双指针比较当前两区间:交集为 [max(开始), min(结束)],合法则记录;结束早的那组指针后移,推进扫描。

概念解释

  • 双指针:两序列各一指针。
  • 交集端点:左取大、右取小。
  • 推进规则:右端小者先耗尽。

原理流程

  1. i、j 指向两组首区间。
  2. 计算交集,left <= right 则记录。
  3. 右端较小者指针前进。

代码 / 示例

// int l = max(a[0], b[0]), r = min(a[1], b[1]); if (l <= r) add
// if (a[1] < b[1]) i++; else j++;

常见误区

  • 误区:任一组无序也能双指针;正解:两组都需按开始有序。
  • 误区:交集端点取反;正解:左边界取较大开始,右边界取较小结束。

追问

  • Q:复杂度? A:O(m+n),空间为结果集。
  • Q:与合并区间区别? A:合并求并集,这里求交集,推进规则不同。

02.8.1.2-008 区间调度与区间合并排序键为何不同?

一句话结论

调度目标是选最多不重叠子集,按结束时间贪心;合并目标是把所有重叠区间连成整体,按开始时间扫描维护右边界;目标不同导致排序键与扫描方向不同。

概念解释

  • 子集选择:丢弃部分区间,需兼容性最优。
  • 全体合并:保留所有区间,只需归并相邻重叠。
  • 键映射目标:结束最早 vs 开始有序。

原理流程

  1. 明确目标是“选子集”还是“合并全体”。
  2. 选子集 → 结束排序;合并 → 开始排序。
  3. 分别套用扫描规则。

代码 / 图示

调度:结束升序 + 兼容选择;合并:开始升序 + 右边界维护

常见误区

  • 误区:两类题共用同一排序模板;正解:先判目标再选键。
  • 误区:合并也按结束排序;正解:结束排序后左端点无序,无法顺序归并。

追问

  • Q:覆盖问题用哪个键? A:开始排序,候选内取右端最远。
  • Q:箭数问题用哪个键? A:右端排序,与调度同构。

02.8.1.2-009 任务调度器(冷却时间)怎么贪?

一句话结论

同类任务需间隔 n 个其他任务;优先安排出现次数最多的任务填充冷却槽,用最大堆按剩余次数取任务,按轮次冷却调度;最少总时间由“最满排法”决定。

概念解释

  • 冷却:相同任务两次执行间隔 >= n+1。
  • 高频优先:先解决出现次数最多者,避免其填满所有槽位。
  • 槽位:每轮 n+1 个执行位置。

原理流程

  1. 统计任务频次入最大堆。
  2. 每轮取最多 n+1 个不同任务执行,次数减一。
  3. 剩余任务入下一轮,累计时间。

代码 / 示例

maxFreq 任务构造框架,空闲槽由次高频任务填充;槽位不足时总时间 = 任务数

常见误区

  • 误区:按任务出现顺序调度;正解:必须优先安排高频任务,否则冷却冲突。
  • 误区:冷却期内不能安排任何任务;正解:可安排其他不同类任务。

追问

  • Q:公式法结论? A:时间 = max(任务总数, (maxFreq-1)*(n+1) + 出现次数等于 maxFreq 的任务数)。
  • Q:复杂度? A:堆模拟 O(时间 × log k),公式法 O(n)。

02.8.1.2-010 带截止时间的任务最大收益怎么贪?

一句话结论

按收益降序考虑任务,用并查集或时间桶把任务安排在不晚于截止时间的最晚可用空位;能放下则计入收益;等价于“收益高者优先占用最近空位”。

概念解释

  • 截止时间:任务必须在该时刻前完成。
  • 最晚空位:尽量靠右放,保留早段给截止更早的任务。
  • 收益优先:高收益任务先选位。

原理流程

  1. 任务按收益降序。
  2. 对每个任务找 <= 截止时间的最晚空位。
  3. 有空位则安排并累加收益,无空位跳过。

代码 / 示例

并查集指向上一个可用空位;找不到 0 空位则放弃

常见误区

  • 误区:按截止时间排序安排;正解:收益优先选任务,空位查找负责可行性。
  • 误区:任务可任意时长;正解:每题任务耗时默认 1 单位,时长不同需改模型。

追问

  • Q:时间复杂度? A:排序 O(n log n),空位查找近 O(1)(并查集路径压缩)。
  • Q:若任务时长不等? A:需 DP 或更复杂调度模型。

02.8.1.2-011 跳跃游戏 I 可达性怎么判?

一句话结论

维护可达最远下标;扫描中不可达即失败,否则用 i+nums[i] 扩展边界,覆盖末位即成功;边界单调右扩,判定覆盖全部可达位置。

概念解释

  • 可达区间:起点能到达的下标连续范围。
  • 最远边界:区间右端。
  • 判定:末位是否落入可达区间。

原理流程

  1. far = 0。
  2. i > far 返回 false。
  3. 更新 far,达到末位返回 true。

代码 / 示例

boolean canJump(int[] nums) {
    int far = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > far) return false;
        far = Math.max(far, i + nums[i]);
    }
    return true;
}

常见误区

  • 误区:每步只看当前格能跳多远;正解:维护整段可达区间边界。
  • 误区:遇到 0 直接失败;正解:0 未越过已覆盖边界即可达。

追问

  • Q:复杂度? A:O(n) 时间,O(1) 空间。
  • Q:与最少跳跃题区别? A:本题只判可达,不计数。

02.8.1.2-012 跳跃游戏 II 最少跳跃次数怎么贪?

一句话结论

按 BFS 分层:维护当前层右边界 curEnd 与下一步最远 nextFar;扫描过当前层边界时跳数加一并把 nextFar 升为新边界;一次扫描得到最少次数。

概念解释

  • 层:一次跳跃能到达的下标范围。
  • nextFar:当前层内各位置可达的最远值。
  • 分层推进等价于 BFS 最短跳数。

原理流程

  1. jumps = 0, curEnd = 0, nextFar = 0。
  2. 扫描 i,更新 nextFar。
  3. 到达 curEnd 时 jumps++,curEnd = nextFar。

代码 / 示例

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

常见误区

  • 误区:每步都选跳最远的格子;正解:最优解可能在当前层内选某一格铺出更远边界,需整层扫描。
  • 误区:在最后一个元素处也计数;正解:循环到 n-2,到达末位无需再跳。

追问

  • Q:复杂度? A:O(n) 时间,O(1) 空间。
  • Q:为什么等价 BFS? A:同层节点跳跃次数相同,边界推进即层扩展。

02.8.1.2-013 分发糖果(LC 135)双向贪心怎么做?

一句话结论

每个孩子分数高于邻居则糖更多;先从左到右保证右侧高分拿更多,再从右到左保证左侧高分拿更多,两轮取最大值,即满足两侧约束的最少糖果。

概念解释

  • 左到右:处理 i 比 i-1 高分。
  • 右到左:处理 i 比 i+1 高分。
  • 取 max:两轮结果合并,避免单侧覆盖另一侧。

原理流程

  1. 每人初始 1 颗。
  2. 左扫:rating[i] > rating[i-1] 则 candy[i] = candy[i-1]+1。
  3. 右扫:rating[i] > rating[i+1] 则 candy[i] = max(candy[i], candy[i+1]+1),求和。

代码 / 示例

int[] c = new int[n]; Arrays.fill(c, 1);
for (int i = 1; i < n; i++) if (r[i] > r[i-1]) c[i] = c[i-1]+1;
for (int i = n-2; i >= 0; i--) if (r[i] > r[i+1]) c[i] = Math.max(c[i], c[i+1]+1);

常见误区

  • 误区:一轮左扫即可;正解:右邻约束未处理,会少发糖。
  • 误区:右扫直接覆盖左扫结果;正解:取 max,保留两侧较大要求。

追问

  • Q:分数相等糖果要求? A:题意只要求高分更多,相等可不等。
  • Q:复杂度? A:O(n) 时间,O(n) 空间。

02.8.1.2-014 加油站(LC 134)怎么贪?

一句话结论

全程油量结余小于 0 则无解;从起点累加剩余油量,一旦结余为负,说明当前起点到此处不可行,起点移到下一位置并清零结余;可行起点必在最后一次断油位置之后。

概念解释

  • 剩余量:gas[i] - cost[i]。
  • 段结余:连续累加。
  • 总前提:全局结余 >= 0。

原理流程

  1. 先校验 total >= 0。
  2. tank 累加,为负则 start = i+1,tank 清零。
  3. 遍历结束返回 start。

代码 / 示例

int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int d = gas[i] - cost[i];
        total += d; tank += d;
        if (tank < 0) { start = i + 1; tank = 0; }
    }
    return total >= 0 ? start : -1;
}

常见误区

  • 误区:从每个站模拟一圈判断;正解:断油段内所有起点都不可行,整体移动起点即可。
  • 误区:总结余 >= 0 就任意起点可行;正解:起点影响顺序,需定位可行起点。

追问

  • Q:为什么断油点之后才可能是起点? A:断油段内任一点出发仍会再次缺油,被段内负结余拖垮。
  • Q:复杂度? A:O(n) 时间,O(1) 空间。

02.8.1.2-015 买卖股票 II(多次交易)贪心怎么理解?

一句话结论

不限交易次数且不能同时持有,只要后一天价格高于前一天就计入这一段涨幅;把所有相邻正价差累加,等价于低买高卖捕获全部上涨段。

概念解释

  • 无冷冻期、可当天卖了再买。
  • 相邻价差:profit[i] = max(0, prices[i]-prices[i-1])。
  • 累加正差即最优。

原理流程

  1. 遍历相邻价格。
  2. 正价差累加,负价差跳过。
  3. 输出总和。

代码 / 示例

int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++)
        profit += Math.max(0, prices[i] - prices[i-1]);
    return profit;
}

常见误区

  • 误区:必须找全局最低点和最高点;正解:分段累计相邻正差与整段持有收益等价。
  • 误区:当天可先卖再买产生额外收益;正解:相邻正差已等价覆盖,不重复计。

追问

  • Q:有限交易次数还能这样贪吗? A:不能,需 DP 状态机,见 02.7.1.4。
  • Q:复杂度? A:O(n) 时间,O(1) 空间。

02.8.1.2-016 分配饼干(LC 455)怎么贪?

一句话结论

胃口与饼干都升序排序;用最小能满足当前胃口的饼干去喂,双指针推进;小饼干不够当前胃口就继续找下一块,保证大饼干留给大胃口。

概念解释

  • 胃口 g:最低要求。
  • 饼干 s:实际大小。
  • 匹配:s[j] >= g[i]。

原理流程

  1. 两数组升序。
  2. 胃口指针 i,饼干指针 j。
  3. 够则双进,不够饼干指针前进。

代码 / 示例

int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g); Arrays.sort(s);
    int i = 0, j = 0;
    while (i < g.length && j < s.length) {
        if (s[j] >= g[i]) i++;
        j++;
    }
    return i;
}

常见误区

  • 误区:用大饼干优先满足小胃口;正解:大饼干留给大胃口,避免浪费。
  • 误区:饼干不排序也能双指针;正解:需有序才能依次匹配。

追问

  • Q:复杂度? A:O(n log n + m log m) 排序,O(n+m) 扫描。
  • Q:匹配数上限? A:min(孩子数, 饼干数)。

02.8.1.2-017 划分字母区间(LC 763)怎么做?

一句话结论

先统计每个字母最后出现位置;从左扫描,维护当前段最远右边界,遇到边界内字母的更后出现位置则扩展;扫描到边界即切出一段,再开新段。

概念解释

  • 最后位置:字母不再出现的最右下标。
  • 段边界:段内所有字母最后位置的最大值。
  • 切分:边界到达时该字母不会再出现在后续段。

原理流程

  1. 记录 last[char]。
  2. start = 0,end = 0,遍历 i 更新 end = max(end, last[s[i]])。
  3. i == end 记录段长,start = i+1。

代码 / 示例

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> res = new ArrayList<>();
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        end = Math.max(end, last[s.charAt(i)-'a']);
        if (i == end) { res.add(end - start + 1); start = i + 1; }
    }
    return res;
}

常见误区

  • 误区:按字母首次出现位置切段;正解:必须覆盖到该字母最后出现位置。
  • 误区:段边界只看当前字母;正解:取段内所有字母 last 的最大值。

追问

  • Q:复杂度? A:O(n) 时间,O(1) 字符表空间。
  • Q:为什么这样切段数最多且合法? A:每段是不能再拆的最小合法单位,拆分必然割裂某字母。

02.8.1.2-018 会议室安排与区间调度有何异同?

一句话结论

会议室数量求最大并行深度,事件 +1/-1 或堆维护结束时间;区间调度求最多不重叠子集,按结束时间选择;一个算资源峰值,一个算兼容选择,都基于区间排序扫描。

概念解释

  • 峰值:同一时刻并行数。
  • 子集:互不重叠的最大个数。
  • 共享工具:排序、结束时间维护。

原理流程

  1. 判目标:需要多少间房 vs 最多排多少场。
  2. 房间数:事件计数或堆复用。
  3. 调度:结束排序选择。

代码 / 图示

房间数:开始 +1 结束 -1 取峰值;调度:结束升序兼容选择

常见误区

  • 误区:两道题互相套用排序;正解:目标不同,事件方向不同。
  • 误区:房间数等于不重叠区间数;正解:二者无直接等式。

追问

  • Q:已排好会议的最早结束时间用什么维护? A:最小堆堆顶。
  • Q:端点相等事件顺序? A:先处理结束再处理开始,避免虚增房间。

02.8.1.2-019 区间类贪心通用扫描框架是什么?

一句话结论

统一框架:按目标选定排序键 → 维护当前边界/候选堆 → 线性扫描决策(选中/合并/扩展/计数)→ 处理端点相等与空输入;先判题目是选择、合并、覆盖还是交集。

概念解释

  • 四目标:选子集、合并全体、覆盖目标、求交集。
  • 边界变量:当前右端、堆顶、双指针。
  • 端点口径:相接是否冲突按题意。

原理流程

  1. 归类目标类型。
  2. 选排序键与数据结构。
  3. 扫描决策并记录结果。

代码 / 图示

排序 → 边界维护 → 扫描决策 → 端点核对

常见误区

  • 误区:一上来就写扫描;正解:先归类目标再套框架。
  • 误区:结果集与计数混淆;正解:选择类保留区间,调度类只计数。

追问

  • Q:区间题最常见边界? A:空数组、单区间、端点相接、完全包含。
  • Q:关联页面? A:前缀与差分见 02.2.1.3,二维矩阵见 02.2.1.4。

02.8.1.2-020 调度类贪心的资源模型怎么抽象?

一句话结论

把调度抽象为“资源槽位 + 任务约束(截止时间/冷却/时长)+ 优化目标(收益/数量/时间)”;先按目标确定优先顺序,再用堆或并查集分配槽位;约束不同模型不同。

概念解释

  • 资源:会议室、时间槽、通道。
  • 约束:截止时间、冷却间隔、执行时长。
  • 目标:最大收益、最少资源、最短总时长。

原理流程

  1. 列资源、约束、目标。
  2. 选优先级指标。
  3. 数据结构分配资源并计数。

代码 / 图示

约束 → 优先级 → 分配结构(堆/并查集/双指针)→ 结果

常见误区

  • 误区:忽略任务时长;正解:时长不等时 1 单位模型失效。
  • 误区:约束只看截止时间;正解:冷却、依赖关系都要纳入模型。

追问

  • Q:冷却约束对应哪类题? A:任务调度器,按轮次填充槽位。
  • Q:收益最大化用什么结构? A:收益排序 + 空位查找(堆或并查集)。