class Solution {
public:
int intersectionSizeTwo(vector<vector<int>>& intervals) {
}
};
757. 设置交集大小至少为2
一个整数区间 [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]范围内的整数。原站题解
javascript 解法, 执行用时: 76 ms, 内存消耗: 47.6 MB, 提交时间: 2023-06-12 16:10:14
/**
* @param {number[][]} intervals
* @return {number}
*/
var intersectionSizeTwo = function(intervals) {
const n = intervals.length;
let res = 0;
let m = 2;
intervals.sort((a, b) => {
if (a[0] === b[0]) {
return b[1] - a[1];
}
return a[0] - b[0];
});
const temp = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
temp[i] = [];
}
const help = (intervals, temp, pos, num) => {
for (let i = pos; i >= 0; i--) {
if (intervals[i][1] < num) {
break;
}
temp[i].push(num);
}
}
for (let i = n - 1; i >= 0; i--) {
for (let j = intervals[i][0], k = temp[i].length; k < m; j++, k++) {
res++;
help(intervals, temp, i - 1, j);
}
}
return res;
};
golang 解法, 执行用时: 24 ms, 内存消耗: 6.5 MB, 提交时间: 2023-06-12 16:09:51
func intersectionSizeTwo(intervals [][]int) (ans int) {
sort.Slice(intervals, func(i, j int) bool {
a, b := intervals[i], intervals[j]
return a[0] < b[0] || a[0] == b[0] && a[1] > b[1]
})
n, m := len(intervals), 2
vals := make([][]int, n)
for i := n - 1; i >= 0; i-- {
for j, k := intervals[i][0], len(vals[i]); k < m; k++ {
ans++
for p := i - 1; p >= 0 && intervals[p][1] >= j; p-- {
vals[p] = append(vals[p], j)
}
j++
}
}
return
}
java 解法, 执行用时: 11 ms, 内存消耗: 43.1 MB, 提交时间: 2023-06-12 16:09:35
class Solution {
public int intersectionSizeTwo(int[][] intervals) {
int n = intervals.length;
int res = 0;
int m = 2;
Arrays.sort(intervals, (a, b) -> {
if (a[0] == b[0]) {
return b[1] - a[1];
}
return a[0] - b[0];
});
List<Integer>[] temp = new List[n];
for (int i = 0; i < n; i++) {
temp[i] = new ArrayList<Integer>();
}
for (int i = n - 1; i >= 0; i--) {
for (int j = intervals[i][0], k = temp[i].size(); k < m; j++, k++) {
res++;
help(intervals, temp, i - 1, j);
}
}
return res;
}
public void help(int[][] intervals, List<Integer>[] temp, int pos, int num) {
for (int i = pos; i >= 0; i--) {
if (intervals[i][1] < num) {
break;
}
temp[i].add(num);
}
}
}
python3 解法, 执行用时: 64 ms, 内存消耗: 17.6 MB, 提交时间: 2023-06-12 16:09:14
# 贪心，先对区间排序，
class Solution:
def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: (x[0], -x[1]))
ans, n, m = 0, len(intervals), 2
vals = [[] for _ in range(n)]
for i in range(n - 1, -1, -1):
j = intervals[i][0]
for k in range(len(vals[i]), m):
ans += 1
for p in range(i - 1, -1, -1):
if intervals[p][1] < j:
break
vals[p].append(j)
j += 1
return ans