題目描述
這是 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
是連續段。
為了友善，我們令
intervals
為
ins
。
當隻有一個線段時，我們可以線上段内取任意兩點作為
S
成員，而當隻有兩個線段時，我們可以兩個線段重合情況進行決策：
- 當兩個線段完全不重合時，為滿足題意，我們需要從兩個線段中各取兩個點，此時這四個點都可以任意取；
- 當兩個線段僅有一個點重合，為滿足
S
- 當兩個線段有兩個及以上的點重合，此時在重合點中任選兩個即可。
不難發現，當出現重合的所有情況中，必然可以歸納某個線段的邊緣點上。即不存在兩個線段存在重合點，僅發生在兩線段的中間部分：
是以我們可以從邊緣點決策進行入手。
具體的，我們可以按照「右端點從小到大，左端點從大到小」的雙關鍵字排序，然後從前往後處理每個區間，處理過程中不斷往
S
中添加元素，由于我們已對所有區間排序且從前往後處理，是以我們往
S
中增加元素的過程中必然是單調遞增，同時在對新的後續區間考慮是否需要往
S
中添加元素來滿足題意時，也是與
S
中的最大/次大值（點集中的邊緣元素）做比較，是以我們可以使用兩個變量
a
和
b
分别代指目前集合
S
中的次大值和最大值（
a
和
b
初始化為足夠小的值 ），而無需将整個
S
存下來。
不失一般性的考慮，當我們處理到
- 若（目前區間的左端點大于目前點集
S
S
- 若（即目前區間與點集
S
b
a
b
- 其餘情況，說明目前區間與點集
S
a
b
上述情況是對「右端點從小到大」的必要性說明，而「左端點從大到小」目的是為了友善我們處理邊界情況而引入的：若在右端點相同的情況下，如果「左端點從小到大」處理的話，會有重複的邊緣點被加入
S
。
上述決策存在直覺判斷，需要證明不存在比該做法取得的點集
S
更小的合法解：
若存在更小的合法集合方案
A
（最優解），根據我們最前面對兩個線段的重合分析知道，由于存在任意選點均能滿足覆寫要求的情況，是以最優解
A
的具體方案可能并不唯一。
是以首先我們先在不影響
A
的集合大小的前提下，對具體方案
A
中的非關鍵點（即那些被選擇，但既不是某個具體區間的邊緣點，也不是邊緣點的相鄰點）進行調整（修改為區間邊緣點或邊緣點的相鄰點）。
這樣我們能夠得到一個唯一的最優解具體方案，該方案既能取到最小點集大小，同時與貪心解
S
的選點有較大重合度。
此時如果貪心解并不是最優解的話，意味着貪心解中存在某些不必要的點（可去掉，同時不會影響覆寫要求）。
然後我們在回顧下，我們什麼情況下會往
S
中進行加點，根據上述「不失一般性」的分析：
- 當時，我們會往
S
即此時原本在最優解
A
中不存在，在貪心解
S
中存在的「不必要點」會變成「必要點」。
- 當時，我們會往
S
綜上，我們可以經過兩步的“調整”，将貪心解變為最優解：第一步調整是在最優解的任意具體方案
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 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 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。
在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。