LeetCode 757. 设置交集大小至少为2
题目描述
题意分析
选择尽可能少的整数，使每个给定闭区间都至少包含其中两个不同整数。
解法：排序 + 贪心维护最后两个点
核心思路
[!blue]
按右端点升序处理区间，同右端时按左端点降序，让更紧的区间先处理。对当前
[l, r]，之前选入的所有点都不超过r，所以只需记录最大的两个点s < e，就能判断当前区间已覆盖了几个点。
- 若
l <= s，最大的两个点都在区间内，已经满足要求，不补点。- 若
s < l <= e，只有最大点e落在区间内，至少还需一个点，选择r，再令s = e、e = r。- 若
e < l，所有旧点都在区间左侧，至少还需两个点，选择r-1、r，并将它们作为新的最大两点。缺几个点就至少要增加几个点，剩下只需证明新增点应尽量靠右。固定已经选中的点，将某个最优补全方案为当前区间提供的缺失点，换到当前区间最右侧的可选位置：此前区间已由固定点满足；后续区间的右端不小于
r，新增点向右移动后仍不超过它们的右端，也不会更容易落到它们左端之外。因此这种替换不会增加点数或破坏已有覆盖，贪心选择能够保留一个最优解。同右端的左端降序保证了只缺一个点时
e < r，从而补入的r是新点。若e已经等于r，它来自此前同右端、左端更大的区间；满足那个更紧区间的两个点也都在当前区间内，应当直接进入不补点的分支，不会再次添加同一个r。题目保证
l < r，所以r-1与r是当前区间内两个不同整数。左端点均非负，初始的s = e = -1只表示尚未选择点，第一个区间会正常补入两个点。
解题步骤
- 按右端升序、左端降序排序。
- 维护已选点中最大的两个点和答案数量。
- 已有至少两个点落入区间时跳过。
- 只覆盖一个点就补一个，否则补右端相邻的两个点。
代码实现
class Solution {
public int intersectionSizeTwo(int[][] intervals) {
// 右端升序，同右端先处理左端更大的紧区间。
Arrays.sort(intervals, (a, b) -> a[1] != b[1] ? a[1] - b[1] : b[0] - a[0]);
int answer = 0;
int s = -1;
int e = -1;
for (int[] it : intervals) {
int l = it[0];
int r = it[1];
// 最大的两个已选点都落在区间中，无需再补点。
if (l <= s) {
continue;
}
// 只有一个点被覆盖时补右端，否则补右端附近两个点。
if (l <= e) {
answer += 1;
s = e;
e = r;
} else {
answer += 2;
s = r - 1;
e = r;
}
}
return answer;
}
}
import "sort"
func intersectionSizeTwo(intervals [][]int) int {
// 右端升序，同右端先处理左端更大的紧区间。
sort.Slice(intervals, func(i, j int) bool {
if intervals[i][1] != intervals[j][1] {
return intervals[i][1] < intervals[j][1]
}
return intervals[i][0] > intervals[j][0]
})
answer := 0
s, e := -1, -1
for _, interval := range intervals {
l, r := interval[0], interval[1]
// 最大的两个已选点都落在区间中，无需再补点。
if l <= s {
continue
}
// 只有一个点被覆盖时补右端，否则补右端附近两个点。
if l <= e {
answer++
s = e
e = r
} else {
answer += 2
s = r - 1
e = r
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n\log(n+1))$，
n为区间数，排序后线性扫描。- 空间复杂度：扫描辅助空间 $O(1)$；Java 对象数组排序工作区为 $O(n)$，Go 排序栈为 $O(\log(n+1))$。
关键点总结
[!green]
- 两个点必须不同，同右端的排序规则避免重复补入已有右端。
- 不必保存全部选点，最大的两个足以判断当前覆盖情况。
- 区间是闭区间，端点本身可以被选取。
易错点总结
[!yellow]
- 缺两个点时选左端附近：会减少对后续区间的复用。
- 同右端不先处理更紧区间：补点分支可能重复选到同一个右端。
- 只记录最大的一个点：无法区分当前覆盖一个还是至少两个。
- 使用严格大于判断点在左端内：遗漏端点相等的合法覆盖。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 452. 用最少数量的箭引爆气球 | 中等 | 原题每个区间至少命中一个点，本题至少两个点，可继续按右端点贪心并维护最近选择。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！