关于后端:757-设置交集大小至少为2-贪心运用题

5次阅读

共计 3171 个字符，预计需要花费 8 分钟才能阅读完成。

这是 LeetCode 上的 757. 设置交加大小至多为 2 ，难度为艰难。

Tag :「贪婪」

一个整数区间 $[a, b]$ ($a < b$) 代表着从 a 到 b 的所有间断整数，包含 a 和 b。

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

输入这个最小汇合 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 的长度范畴为 $[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 更小的非法解 ：

若存在更小的非法汇合计划 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 代码：

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