02.8.1.2 区间与调度贪心
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.8 贪心与技巧题 / 02.8.1 贪心与技巧
02.8.1.2-001 最多不重叠区间怎么选?
一句话结论
按结束时间升序,依次选与已选区间不冲突的区间;结束最早者给后续留最多空间,得到最多不重叠区间数。
概念解释
- 冲突:两区间有公共点。
- 兼容:后一开始不早于前一结束。
- 目标:区间数量最大。
原理流程
- 按右端点升序排序。
- end 记录已选最右边界。
- 当前左端点 >= 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 合并重叠区间怎么做?
一句话结论
按开始时间升序,维护当前合并区间的右边界;下一区间开始不超过右边界则合并并扩展右边界,否则封存当前区间开启新区间。
概念解释
- 开始排序:保证左侧已处理,只需比较右端。
- 右边界扩展:取两者右端较大值。
- 目标:输出互不重叠的合并结果。
原理流程
- 按左端点升序。
- 结果集空则压入首区间。
- 比较当前区间与结果末区间右端,重叠则合并,否则追加。
代码 / 示例
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 向有序区间集插入新区间并合并怎么做?
一句话结论
先加入所有结束早于新区间开始的区间,再合并所有与新区间重叠的区间(更新左右边界),最后追加剩余区间;无需重排,一次线性扫描。
概念解释
- 前段:不重叠且在左侧。
- 中段:与新区间相交,合并边界。
- 后段:在右侧不重叠。
原理流程
- 复制输入并加入新区间,或分段扫描原有序数组。
- 前段追加 → 中段合并 → 后段追加。
- 输出合并结果。
代码 / 示例
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 类)怎么贪?
一句话结论
按右端点升序,一支箭打在当前区间右端;后续区间开始不超过该右端则被同支覆盖,否则开新箭;与区间调度同构,目标是最少箭数。
概念解释
- 一箭覆盖一批右端相接/包含的区间。
- 右端排序:最早结束处放箭,覆盖后续尽可能多气球。
- 目标:箭数最少。
原理流程
- 按右端升序。
- 首箭定在首区间右端。
- 后续开始 > 当前箭位则新增箭并更新位置。
代码 / 示例
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
常见误区
- 误区:开始与结束同时发生时先加后减;正解:会议结束即释放,应先 -1,避免高估房间数。
- 误区:会议室数等于区间总数;正解:只算并行峰值。
追问
- Q:事件扫描复杂度? A:O(n log n) 排序,O(n) 扫描。
- Q:堆法复杂度? A:O(n log n),堆大小为并行会议数。
02.8.1.2-006 最少区间覆盖整条目标区间怎么选?
一句话结论
在当前覆盖右边界内,选开始不超过当前边界且右端最远的区间,扩展覆盖;每次选跨度贡献最大者,直到覆盖目标左端到右端。
概念解释
- 当前边界:已覆盖到的最右位置。
- 候选:开始 <= 当前边界的区间。
- 扩展目标:右端尽可能远。
原理流程
- 按开始排序。
- 每轮在候选内取右端最远,更新边界。
- 边界未推进则无法覆盖,返回失败。
代码 / 示例
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(结束)],合法则记录;结束早的那组指针后移,推进扫描。
概念解释
- 双指针:两序列各一指针。
- 交集端点:左取大、右取小。
- 推进规则:右端小者先耗尽。
原理流程
- i、j 指向两组首区间。
- 计算交集,left <= right 则记录。
- 右端较小者指针前进。
代码 / 示例
// 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 开始有序。
原理流程
- 明确目标是“选子集”还是“合并全体”。
- 选子集 → 结束排序;合并 → 开始排序。
- 分别套用扫描规则。
代码 / 图示
调度:结束升序 + 兼容选择;合并:开始升序 + 右边界维护
常见误区
- 误区:两类题共用同一排序模板;正解:先判目标再选键。
- 误区:合并也按结束排序;正解:结束排序后左端点无序,无法顺序归并。
追问
- Q:覆盖问题用哪个键? A:开始排序,候选内取右端最远。
- Q:箭数问题用哪个键? A:右端排序,与调度同构。
02.8.1.2-009 任务调度器(冷却时间)怎么贪?
一句话结论
同类任务需间隔 n 个其他任务;优先安排出现次数最多的任务填充冷却槽,用最大堆按剩余次数取任务,按轮次冷却调度;最少总时间由“最满排法”决定。
概念解释
- 冷却:相同任务两次执行间隔 >= n+1。
- 高频优先:先解决出现次数最多者,避免其填满所有槽位。
- 槽位:每轮 n+1 个执行位置。
原理流程
- 统计任务频次入最大堆。
- 每轮取最多 n+1 个不同任务执行,次数减一。
- 剩余任务入下一轮,累计时间。
代码 / 示例
maxFreq 任务构造框架,空闲槽由次高频任务填充;槽位不足时总时间 = 任务数
常见误区
- 误区:按任务出现顺序调度;正解:必须优先安排高频任务,否则冷却冲突。
- 误区:冷却期内不能安排任何任务;正解:可安排其他不同类任务。
追问
- Q:公式法结论? A:时间 = max(任务总数, (maxFreq-1)*(n+1) + 出现次数等于 maxFreq 的任务数)。
- Q:复杂度? A:堆模拟 O(时间 × log k),公式法 O(n)。
02.8.1.2-010 带截止时间的任务最大收益怎么贪?
一句话结论
按收益降序考虑任务,用并查集或时间桶把任务安排在不晚于截止时间的最晚可用空位;能放下则计入收益;等价于“收益高者优先占用最近空位”。
概念解释
- 截止时间:任务必须在该时刻前完成。
- 最晚空位:尽量靠右放,保留早段给截止更早的任务。
- 收益优先:高收益任务先选位。
原理流程
- 任务按收益降序。
- 对每个任务找 <= 截止时间的最晚空位。
- 有空位则安排并累加收益,无空位跳过。
代码 / 示例
并查集指向上一个可用空位;找不到 0 空位则放弃
常见误区
- 误区:按截止时间排序安排;正解:收益优先选任务,空位查找负责可行性。
- 误区:任务可任意时长;正解:每题任务耗时默认 1 单位,时长不同需改模型。
追问
- Q:时间复杂度? A:排序 O(n log n),空位查找近 O(1)(并查集路径压缩)。
- Q:若任务时长不等? A:需 DP 或更复杂调度模型。
02.8.1.2-011 跳跃游戏 I 可达性怎么判?
一句话结论
维护可达最远下标;扫描中不可达即失败,否则用 i+nums[i] 扩展边界,覆盖末位即成功;边界单调右扩,判定覆盖全部可达位置。
概念解释
- 可达区间:起点能到达的下标连续范围。
- 最远边界:区间右端。
- 判定:末位是否落入可达区间。
原理流程
- far = 0。
- i > far 返回 false。
- 更新 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 最短跳数。
原理流程
- jumps = 0, curEnd = 0, nextFar = 0。
- 扫描 i,更新 nextFar。
- 到达 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 颗。
- 左扫:rating[i] > rating[i-1] 则 candy[i] = candy[i-1]+1。
- 右扫: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。
原理流程
- 先校验 total >= 0。
- tank 累加,为负则 start = i+1,tank 清零。
- 遍历结束返回 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])。
- 累加正差即最优。
原理流程
- 遍历相邻价格。
- 正价差累加,负价差跳过。
- 输出总和。
代码 / 示例
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]。
原理流程
- 两数组升序。
- 胃口指针 i,饼干指针 j。
- 够则双进,不够饼干指针前进。
代码 / 示例
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)怎么做?
一句话结论
先统计每个字母最后出现位置;从左扫描,维护当前段最远右边界,遇到边界内字母的更后出现位置则扩展;扫描到边界即切出一段,再开新段。
概念解释
- 最后位置:字母不再出现的最右下标。
- 段边界:段内所有字母最后位置的最大值。
- 切分:边界到达时该字母不会再出现在后续段。
原理流程
- 记录 last[char]。
- start = 0,end = 0,遍历 i 更新 end = max(end, last[s[i]])。
- 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 或堆维护结束时间;区间调度求最多不重叠子集,按结束时间选择;一个算资源峰值,一个算兼容选择,都基于区间排序扫描。
概念解释
- 峰值:同一时刻并行数。
- 子集:互不重叠的最大个数。
- 共享工具:排序、结束时间维护。
原理流程
- 判目标:需要多少间房 vs 最多排多少场。
- 房间数:事件计数或堆复用。
- 调度:结束排序选择。
代码 / 图示
房间数:开始 +1 结束 -1 取峰值;调度:结束升序兼容选择
常见误区
- 误区:两道题互相套用排序;正解:目标不同,事件方向不同。
- 误区:房间数等于不重叠区间数;正解:二者无直接等式。
追问
- Q:已排好会议的最早结束时间用什么维护? A:最小堆堆顶。
- Q:端点相等事件顺序? A:先处理结束再处理开始,避免虚增房间。
02.8.1.2-019 区间类贪心通用扫描框架是什么?
一句话结论
统一框架:按目标选定排序键 → 维护当前边界/候选堆 → 线性扫描决策(选中/合并/扩展/计数)→ 处理端点相等与空输入;先判题目是选择、合并、覆盖还是交集。
概念解释
- 四目标:选子集、合并全体、覆盖目标、求交集。
- 边界变量:当前右端、堆顶、双指针。
- 端点口径:相接是否冲突按题意。
原理流程
- 归类目标类型。
- 选排序键与数据结构。
- 扫描决策并记录结果。
代码 / 图示
排序 → 边界维护 → 扫描决策 → 端点核对
常见误区
- 误区:一上来就写扫描;正解:先归类目标再套框架。
- 误区:结果集与计数混淆;正解:选择类保留区间,调度类只计数。
追问
- Q:区间题最常见边界? A:空数组、单区间、端点相接、完全包含。
- Q:关联页面? A:前缀与差分见 02.2.1.3,二维矩阵见 02.2.1.4。
02.8.1.2-020 调度类贪心的资源模型怎么抽象?
一句话结论
把调度抽象为“资源槽位 + 任务约束(截止时间/冷却/时长)+ 优化目标(收益/数量/时间)”;先按目标确定优先顺序,再用堆或并查集分配槽位;约束不同模型不同。
概念解释
- 资源:会议室、时间槽、通道。
- 约束:截止时间、冷却间隔、执行时长。
- 目标:最大收益、最少资源、最短总时长。
原理流程
- 列资源、约束、目标。
- 选优先级指标。
- 数据结构分配资源并计数。
代码 / 图示
约束 → 优先级 → 分配结构(堆/并查集/双指针)→ 结果
常见误区
- 误区:忽略任务时长;正解:时长不等时 1 单位模型失效。
- 误区:约束只看截止时间;正解:冷却、依赖关系都要纳入模型。
追问
- Q:冷却约束对应哪类题? A:任务调度器,按轮次填充槽位。
- Q:收益最大化用什么结构? A:收益排序 + 空位查找(堆或并查集)。