目标
给你一个二维整数数组 intervals ，其中 intervals[i] = [starti, endi] 表示从 starti 到 endi 的所有整数，包括 starti 和 endi 。
包含集合 是一个名为 nums 的数组，并满足 intervals 中的每个区间都 至少 有 两个 整数在 nums 中。
- 例如，如果 intervals = [[1,3], [3,7], [8,9]] ，那么 [1,2,4,7,8,9] 和 [2,3,4,8,9] 都符合 包含集合 的定义。
返回包含集合可能的最小大小。
示例 1：
输入：intervals = [[1,3],[3,7],[8,9]]
输出：5
解释：nums = [2, 3, 4, 8, 9].
可以证明不存在元素数量为 4 的包含集合。示例 2：
输入：intervals = [[1,3],[1,4],[2,5],[3,5]]
输出：3
解释：nums = [2, 3, 4].
可以证明不存在元素数量为 2 的包含集合。 示例 3：
输入：intervals = [[1,2],[2,3],[2,4],[4,5]]
输出：5
解释：nums = [1, 2, 3, 4, 5].
可以证明不存在元素数量为 4 的包含集合。 说明：
- 1 <= intervals.length <= 3000
- intervals[i].length == 2
- 0 <= starti < endi <= 10^8
思路
定义包含集合是 与 intervals 中每个区间的交集大小至少为 2 的集合，求包含集合的最小 size。
根据 intervals 中每个区间的起点排序，倒序遍历区间，对于最后一个区间，显然优先选最左边的 2 个元素最优，将其按照从大到小顺序加入包含列表，接着访问下一个区间，判断包含集合的最小的两个元素是否在当前区间内：
- 如果都在，直接跳过
- 如果都不在，将当前区间左侧前两个元素按从大到小顺序加入包含列表
- 如果只有一个在，需要比较当前区间左端点
l与包含集合最小元素min的关系，如果min > l将l加入列表，否则（即min == l，由于是按起点排序的，所以min不会小于l），用l + 1替换原来的列表最后一个元素，然后将l加入列表
代码
/**
* @date 2025-11-20 8:46
*/
public class IntersectionSizeTwo757 {
public int intersectionSizeTwo(int[][] intervals) {
int n = intervals.length;
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<Integer> res = new ArrayList<>();
int p = 0;
for (int i = n - 1; i >= 0; i--) {
int l = intervals[i][0];
int r = intervals[i][1];
if (p == 0 || res.get(p - 1) > r) {
res.add(l + 1);
res.add(l);
p += 2;
} else if (p > 1 && res.get(p - 2) > r) {
if (res.get(p - 1) == l) {
res.set(p - 1, l + 1);
}
res.add(l);
p++;
}
}
return res.size();
}
}
性能
