LC 757. 设置交集大小至少为2
题目描述
这是 LeetCode 上的 757. 设置交集大小至少为2 ，难度为 困难。
一个整数区间 $[a, b]$ ($a < b$) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。
给你一组整数区间 intervals，请找到一个最小的集合 S，使得 S 里的元素与区间 intervals 中的每一个整数区间都至少有 $2$ 个元素相交。
输出这个最小集合 S 的大小。
示例 1:1
2
3
4
5
6
7输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
输出: 3
解释:
考虑集合 S = {2, 3, 4}. S与intervals中的四个区间都有至少2个相交的元素。
且这是S最小的情况，故我们输出3。
示例 2:1
2
3
4
5
6输入: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
输出: 5
解释:
最小的集合S = {1, 2, 3, 4, 5}.
注意:
intervals的长度范围为 $[1, 3000]$。intervals[i]长度为 $2$，分别代表左、右边界。intervals[i][j]的值是 $[0, 10^8]$ 范围内的整数。
贪心
不要被样例数据误导了，题目要我们求最小点集的数量，并不规定点集 S 是连续段。
为了方便，我们令 intervals 为 ins。
当只有一个线段时，我们可以在线段内取任意两点作为 S 成员，而当只有两个线段时，我们可以两个线段重合情况进行决策：
- 当两个线段完全不重合时，为满足题意，我们需要从两个线段中各取两个点，此时这四个点都可以任意取；
- 当两个线段仅有一个点重合，为满足
S最小化的题意，我们可以先取重合点，然后再两个线段中各取一个； - 当两个线段有两个及以上的点重合，此时在重合点中任选两个即可。
不难发现，当出现重合的所有情况中，必然可以归纳某个线段的边缘点上。即不存在两个线段存在重合点，仅发生在两线段的中间部分：
因此我们可以从边缘点决策进行入手。
具体的，我们可以按照「右端点从小到大，左端点从大到小」的双关键字排序，然后从前往后处理每个区间，处理过程中不断往 S 中添加元素，由于我们已对所有区间排序且从前往后处理，因此我们往 S 中增加元素的过程中必然是单调递增，同时在对新的后续区间考虑是否需要往 S 中添加元素来满足题意时，也是与 S 中的最大/次大值（点集中的边缘元素）做比较，因此我们可以使用两个变量 a 和 b 分别代指当前集合 S 中的次大值和最大值（a 和 b 初始化为足够小的值 $-1$），而无需将整个 S 存下来。
不失一般性的考虑，当我们处理到 $ins[i]$ 时，该如何决策：
- 若 $ins[i][0] > b$（当前区间的左端点大于当前点集
S的最大值），说明 $ins[i]$ 完全不被S所覆盖，为满足题意，我们要在 $ins[i]$ 中选两个点，此时直观思路是选择 $ins[i]$ 最靠右的两个点（即 $ins[i][1] - 1$ 和 $ins[i][1]$）； - 若 $ins[i][0] > a$（即当前区间与点集
S存在一个重合点b，由于次大值a和 最大值b不总是相差 $1$，我们不能写成 $ins[i][0] == b$），此时为了满足 $ins[i]$ 至少被 $2$ 个点覆盖，我们需要在 $ins[i]$ 中额外选择一个点，此时直观思路是选择 $ins[i]$ 最靠右的点（即$ins[i][1]$）； - 其余情况，说明当前区间 $ins[i]$ 与点集
S至少存在两个点a和b，此时无须额外引入其余点来覆盖 $ins[i]$。
上述情况是对「右端点从小到大」的必要性说明，而「左端点从大到小」目的是为了方便我们处理边界情况而引入的：若在右端点相同的情况下，如果「左端点从小到大」处理的话，会有重复的边缘点被加入 S。
有同学对重复边缘点加入
S不理解，假设S当前的次大值和最大值分别为j和k（其中 $k - j > 1$），如果后面有两个区间分别为 $[k - 1, d]$ 和 $[k + 1, d]$ 时，就会出现问题（其中d为满足条件的任意右端点）
更具体的：假设当前次大值和最大值分别为 $2$ 和 $4$，后续两个区间分别为 $[3, 8]$ 和 $[5, 8]$，你会发现先处理 $[3, 8]$ 的话，数值 $8$ 会被重复添加
上述决策存在直观判断，需要证明不存在比该做法取得的点集 S 更小的合法解：
若存在更小的合法集合方案 A（最优解），根据我们最前面对两个线段的重合分析知道，由于存在任意选点均能满足覆盖要求的情况，因此最优解 A 的具体方案可能并不唯一。
因此首先我们先在不影响 A 的集合大小的前提下，对具体方案 A 中的非关键点（即那些被选择，但既不是某个具体区间的边缘点，也不是边缘点的相邻点）进行调整（修改为区间边缘点或边缘点的相邻点）。
这样我们能够得到一个唯一的最优解具体方案，该方案既能取到最小点集大小，同时与贪心解 S 的选点有较大重合度。
此时如果贪心解并不是最优解的话，意味着贪心解中存在某些不必要的点（可去掉，同时不会影响覆盖要求）。
然后我们在回顾下，我们什么情况下会往 S 中进行加点，根据上述「不失一般性」的分析：
- 当 $ins[i][0] > b$ 时，我们会往
S中添加两个点，若这个不必要的点是在这个分支中被添加的话，意味着当前 $ins[i]$ 可以不在此时被覆盖，而在后续其他区间 $ins[j]$ 被覆盖时被同步覆盖（其中 $j > i$），此时必然对应了我们重合分析中的后两种情况，可以将原本在 $ins[j]$ 中被选择的点，调整为 $ins[i]$ 的两个边缘点，结果不会变差（覆盖情况不变，点数不会变多）：
即此时原本在最优解 A 中不存在，在贪心解 S 中存在的「不必要点」会变成「必要点」。
- 当 $ins[i] > a$ 时，我们会往
S中添加一个点，若这个不必要的点是在这个分支被添加的话，分析方式同理，且情况 $1$ 不会发生，如果 $ins[i]$ 和 $ins[j]$ 只有一个重合点的话，起始 $ins[i][1]$ 不会是不必要点：
综上，我们可以经过两步的“调整”，将贪心解变为最优解：第一步调整是在最优解的任意具体方案 A 中发生，通过将所有非边缘点调整为边缘点，来得到一个唯一的最优解具体方案；然后通过反证法证明，贪心解 S 中并不存在所谓的可去掉的「不必要点」，从而证明「贪心解大小必然不会大于最优解的大小」，即 $S > A$ 不成立，$S \leq A$ 恒成立，再结合 A 是最优解的前提（$A \leq S$），可得 $S = A$。
Java 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public int intersectionSizeTwo(int[][] ins) {
Arrays.sort(ins, (a, b)->{
return a[1] != b[1] ? a[1] - b[1] : b[0] - a[0];
});
int a = -1, b = -1, ans = 0;
for (int[] i : ins) {
if (i[0] > b) {
a = i[1] - 1; b = i[1];
ans += 2;
} else if (i[0] > a) {
a = b; b = i[1];
ans++;
}
}
return ans;
}
}
TypeScript 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16function intersectionSizeTwo(ins: number[][]): number {
ins = ins.sort((a, b)=> {
return a[1] != b[1] ? a[1] - b[1] : b[0] - a[0]
});
let a = -1, b = -1, ans = 0
for (const i of ins) {
if (i[0] > b) {
a = i[1] - 1; b = i[1]
ans += 2
} else if (i[0] > a) {
a = b; b = i[1]
ans++
}
}
return ans
};
- 时间复杂度：$O(n\log{n})$
- 空间复杂度：$O(\log{n})$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.752 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
