757. 设置交集大小至少为2 : 贪心运用题

757. 设置交集大小至少为2 : 贪心运用题

题目描述

这是 LeetCode 上的 ​​757. 设置交集大小至少为2​​ ，难度为 困难。

Tag : 「贪心」

输出这个最小集合 ​​S​​ 的大小。

示例 1:

输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]输出: 3解释:考虑集合 S = {2, 3, 4}. S与intervals中的四个区间都有至少2个相交的元素。且这是S最小的情况，故我们输出3。

示例 2:

输入: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]输出: 5解释:最小的集合S = {1, 2, 3, 4, 5}.

注意:

贪心

不要被样例数据误导了，题目要我们求最小点集的数量，并不规定点集 ​​S​​ 是连续段。

为了方便，我们令 ​​intervals​​​ 为 ​​ins​​。

当只有一个线段时，我们可以在线段内取任意两点作为 ​​S​​ 成员，而当只有两个线段时，我们可以两个线段重合情况进行决策：

当两个线段完全不重合时，为满足题意，我们需要从两个线段中各取两个点，此时这四个点都可以任意取；当两个线段仅有一个点重合，为满足​​S​​ 最小化的题意，我们可以先取重合点，然后再两个线段中各取一个；当两个线段有两个及以上的点重合，此时在重合点中任选两个即可。

不难发现，当出现重合的所有情况中，必然可以归纳某个线段的边缘点上。即不存在两个线段存在重合点，仅发生在两线段的中间部分：

因此我们可以从边缘点决策进行入手。

上述情况是对「右端点从小到大」的必要性说明，而「左端点从大到小」目的是为了方便我们处理边界情况而引入的：若在右端点相同的情况下，如果「左端点从小到大」处理的话，会有重复的边缘点被加入 ​​S​​。

上述决策存在直观判断，需要证明不存在比该做法取得的点集 ​​S​​ 更小的合法解：

若存在更小的合法集合方案 ​​A​​​（最优解），根据我们最前面对两个线段的重合分析知道，由于存在任意选点均能满足覆盖要求的情况，因此最优解 ​​A​​ 的具体方案可能并不唯一。

因此首先我们先在不影响 ​​A​​ 的集合大小的前提下，对具体方案 ​​A​​ 中的非关键点（即那些被选择，但既不是某个具体区间的边缘点，也不是边缘点的相邻点）进行调整（修改为区间边缘点或边缘点的相邻点）。

这样我们能够得到一个唯一的最优解具体方案，该方案既能取到最小点集大小，同时与贪心解 ​​S​​ 的选点有较大重合度。

此时如果贪心解并不是最优解的话，意味着贪心解中存在某些不必要的点（可去掉，同时不会影响覆盖要求）。

然后我们在回顾下，我们什么情况下会往 ​​S​​ 中进行加点，根据上述「不失一般性」的分析：

即此时原本在最优解 ​​A​​​ 中不存在，在贪心解 ​​S​​ 中存在的「不必要点」会变成「必要点」。

Java 代码：

class 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

TypeScript 代码：

function 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

最后

这是我们「刷穿 LeetCode」系列文章的第 ​​No.752​​ 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：​​github.com/SharingSour…​​ 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。