宫水三叶的刷题日记

V1

2022/07/22阅读:20主题:前端之巅同款

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

题目描述

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

Tag : 「贪心」

一个整数区间    ( ) 代表着从 a 到 b 的所有连续整数,包括 a 和 b

给你一组整数区间 intervals,请找到一个最小的集合 S,使得 S 里的元素与区间 intervals 中的每一个整数区间都至少有 个元素相交。

输出这个最小集合 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}.

注意:

  • intervals 的长度范围为
  • intervals[i] 长度为  ,分别代表左、右边界。
  • intervals[i][j] 的值是  范围内的整数。

贪心

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

为了方便,我们令 intervalsins

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

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

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

image.png
image.png

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

具体的,我们可以按照「右端点从小到大,左端点从大到小」的双关键字排序,然后从前往后处理每个区间,处理过程中不断往 S 中添加元素,由于我们已对所有区间排序且从前往后处理,因此我们往 S 中增加元素的过程中必然是单调递增,同时在对新的后续区间考虑是否需要往 S 中添加元素来满足题意时,也是与 S 中的最大/次大值(点集中的边缘元素)做比较,因此我们可以使用两个变量 ab 分别代指当前集合 S 中的次大值和最大值(ab 初始化为足够小的值 ),而无需将整个 S 存下来。

不失一般性的考虑,当我们处理到 时,该如何决策:

  1. (当前区间的左端点大于当前点集 S 的最大值),说明 完全不被 S 所覆盖,为满足题意,我们要在 中选两个点,此时直观思路是选择 最靠右的两个点(即 );
  2. (即当前区间与点集 S 存在一个重合点 b,由于次大值 a 和 最大值 b 不总是相差 ,我们不能写成 ),此时为了满足 至少被 个点覆盖,我们需要在 中额外选择一个点,此时直观思路是选择 最靠右的点(即 );
  3. 其余情况,说明当前区间 与点集 S 至少存在两个点 ab,此时无须额外引入其余点来覆盖

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

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

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

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

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

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

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

  1. 时,我们会往 S 中添加两个点,若这个不必要的点是在这个分支中被添加的话,意味着当前 可以不在此时被覆盖,而在后续其他区间 被覆盖时被同步覆盖(其中 ),此时必然对应了我们重合分析中的后两种情况,可以将原本在 中被选择的点,调整为 的两个边缘点,结果不会变差(覆盖情况不变,点数不会变多):
image.png
image.png

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

  1. 时,我们会往 S 中添加一个点,若这个不必要的点是在这个分支被添加的话,分析方式同理,且情况 不会发生,如果 只有一个重合点的话,起始 不会是不必要点:
image.png
image.png

综上,我们可以经过两步的“调整”,将贪心解变为最优解:第一步调整是在最优解的任意具体方案 A 中发生,通过将所有非边缘点调整为边缘点,来得到一个唯一的最优解具体方案;然后通过反证法证明,贪心解 S 中并不存在所谓的可去掉的「不必要点」,从而证明「贪心解大小必然不会大于最优解的大小」,即 不成立, 恒成立,再结合 A 是最优解的前提( ),可得

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 ans;
    }
}

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 ans
};
  • 时间复杂度:
  • 空间复杂度:

最后

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

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

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

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

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1