class Solution {
public:
vector<vector<int>> findMaximalUncoveredRanges(int n, vector<vector<int>>& ranges) {
}
};
2655. 寻找最大长度的未覆盖区间
现给你一个长度为 n 的 索引从 0 开始的 数组 nums 和一个 索引从 0 开始的 2 维数组 ranges ，ranges 是 nums 的子区间列表（子区间可能 重叠 ）。
每行 ranges[i] 恰好有两个元素：
ranges[i][0] 表示第i个区间的起始位置（包含）ranges[i][1] 表示第i个区间的结束位置（包含）这些区间覆盖了 nums 的一些元素，并留下了一些 未覆盖 的元素。你的任务是找到所有 最大长度 的未覆盖区间。
返回按起始点 升序排序 的未覆盖区间的二维数组 answer 。
所有 最大长度 的 未覆盖 区间指满足两个条件：
示例 1 ：
输入：n = 10, ranges = [[3,5],[7,8]] 输出：[[0,2],[6,6],[9,9]] 解释：区间 (3,5) 和 (7,8) 都被覆盖，因此如果我们将 nums 简化为一个二进制数组，其中 0 表示未覆盖的元素，1 表示覆盖的元素，则数组变为[0,0,0,1,1,1,0,1,1,0]，在其中我们可以观察到区间 (0,2)，(6,6)和(9,9)未被覆盖。
示例 2 ：
输入：n = 3, ranges = [[0,2]] 输出：[] 解释：在这个例子中，整个 nums 数组都被覆盖，没有未覆盖的元素，所以输出是一个空数组。
示例 3 ：
输入：n = 7, ranges = [[2,4],[0,3]] 输出：[[5,6]] 解释：区间 (0,3) 和 (2,4) 都被覆盖，因此如果我们将 nums 简化为一个二进制数组，其中 0 表示未覆盖的元素，1 表示覆盖的元素，则数组变为[1,1,1,1,1,0,0]，在其中我们可以观察到区间 (5,6) 未被覆盖。
提示：
1 <= n <= 1090 <= ranges.length <= 106ranges[i].length = 20 <= ranges[i][j] <= n - 1ranges[i][0] <= ranges[i][1]原站题解
cpp 解法, 执行用时: 432 ms, 内存消耗: 137.2 MB, 提交时间: 2023-10-22 10:42:57
class Solution {
public:
vector<vector<int>> findMaximalUncoveredRanges(int n, vector<vector<int>>& ranges) {
sort(ranges.begin(), ranges.end(), [&](vector<int>& a, vector<int>& b){
if(a[0] != b[0])
return a[0] < b[0];
return a[1] > b[1];
});
vector<vector<int>> ret;
int right = -1;
for(auto& r: ranges){
if(r[0] <= right + 1){
right = max(right, r[1]);
}
else{
ret.push_back({right + 1, r[0] - 1});
right = r[1];
}
}
if(right < n - 1)
ret.push_back({right + 1, n - 1});
return ret;
}
};
java 解法, 执行用时: 147 ms, 内存消耗: 94.4 MB, 提交时间: 2023-10-22 10:42:44
class Solution {
public int[][] findMaximalUncoveredRanges(int n, int[][] ranges) {
ArrayList<int[]> ints = Arrays.stream(ranges).collect(Collectors.toCollection(ArrayList::new));
// 添加一个头尾，防止额外判断
ints.add(new int[] {n, Integer.MAX_VALUE});
ints.add(new int[] {Integer.MIN_VALUE, -1});
ints.sort(Comparator.comparing(x -> x[0]));
Deque<int[]> deque = new ArrayDeque<>();
// 查看是否可以和上一个数据合并，如果可以就合并
for (int[] range : ints) {
if (!deque.isEmpty() && deque.peekLast()[1] + 1 >= range[0]) {
int[] integerList = deque.removeLast();
deque.addLast(new int[] {Math.min(integerList[0], range[0]), Math.max(integerList[1], range[1])});
}
else {
deque.addLast(range);
}
}
List<int[]> list = new ArrayList<>(deque);
List<int[]> ans = new ArrayList<>();
// 找到两个数组间隙
for (int i = 1; i < list.size(); i++) {
ans.add(new int[]{list.get(i - 1)[1] + 1, list.get(i)[0] - 1});
}
return ans.toArray(int[][]::new);
}
}
python3 解法, 执行用时: 1480 ms, 内存消耗: 82.5 MB, 提交时间: 2023-10-22 10:42:18
class Solution:
def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:
ranges.sort()
res, c = [], 0
for left, r in ranges:
if c<left:
res.append([c, left-1])
if (t:=r+1)>c:c=t
return res+[[c, n-1]] if c<n else res