Question

2655. 寻找最大长度的未覆盖区间

English Version

题目描述

现给你一个长度为 n 的 索引从 0 开始的 数组 nums 和一个 索引从 0 开始的 2 维数组 ranges ，ranges 是 nums 的子区间列表（子区间可能 重叠 ）。

每行 ranges[i] 恰好有两个元素：

• ranges[i][0] 表示第i个区间的起始位置（包含）
• ranges[i][1] 表示第i个区间的结束位置（包含）

这些区间覆盖了 nums 的一些元素，并留下了一些 未覆盖 的元素。你的任务是找到所有 最大长度 的未覆盖区间。

返回按起始点 升序排序 的未覆盖区间的二维数组 answer 。

所有 最大长度 的 未覆盖 区间指满足两个条件：

• 每个未覆盖的元素应该属于 恰好 一个子区间。
• 不存在两个区间 (l1,r1) 和 (l2,r2) 使得 r1+1=l2 。

 

示例 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 <= 109
• 0 <= ranges.length <= 106
• ranges[i].length = 2
• 0 <= ranges[i][j] <= n - 1
• ranges[i][0] <= ranges[i][1]

解法

方法一：排序

我们将所有的区间按照左端点从小到大排序，然后从左到右遍历所有的区间，维护一个变量 $last$ 表示当前已经被覆盖的最右端点，初始时 $last=-1$。如果当前区间的左端点大于 $last+1$，那么说明 $[last+1, l-1]$ 是一个未被覆盖的区间，我们将其加入答案数组中。然后我们更新 $last$ 为当前区间的右端点，继续遍历下一个区间。当遍历完所有的区间后，如果 $last+1 \lt n$，那么说明 $[last+1, n-1]$ 是一个未被覆盖的区间，我们将其加入答案数组中。

最后我们将答案数组返回即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 是数组 $ranges$ 的长度。

class Solution:
  def findMaximalUncoveredRanges(
    self, n: int, ranges: List[List[int]]
  ) -> List[List[int]]:
    ranges.sort()
    last = -1
    ans = []
    for l, r in ranges:
      if last + 1 < l:
        ans.append([last + 1, l - 1])
      last = max(last, r)
    if last + 1 < n:
      ans.append([last + 1, n - 1])
    return ans

class Solution {
  public int[][] findMaximalUncoveredRanges(int n, int[][] ranges) {
    Arrays.sort(ranges, (a, b) -> a[0] - b[0]);
    int last = -1;
    List<int[]> ans = new ArrayList<>();
    for (int[] range : ranges) {
      int l = range[0], r = range[1];
      if (last + 1 < l) {
        ans.add(new int[] {last + 1, l - 1});
      }
      last = Math.max(last, r);
    }
    if (last + 1 < n) {
      ans.add(new int[] {last + 1, n - 1});
    }
    return ans.toArray(new int[0][]);
  }
}

class Solution {
public:
  vector<vector<int>> findMaximalUncoveredRanges(int n, vector<vector<int>>& ranges) {
    sort(ranges.begin(), ranges.end(), [](const vector<int>& a, const vector<int>& b) {
      return a[0] < b[0];
    });
    int last = -1;
    vector<vector<int>> ans;
    for (auto& range : ranges) {
      int l = range[0], r = range[1];
      if (last + 1 < l) {
        ans.push_back({last + 1, l - 1});
      }
      last = max(last, r);
    }
    if (last + 1 < n) {
      ans.push_back({last + 1, n - 1});
    }
    return ans;
  }
};

func findMaximalUncoveredRanges(n int, ranges [][]int) (ans [][]int) {
  sort.Slice(ranges, func(i, j int) bool { return ranges[i][0] < ranges[j][0] })
  last := -1
  for _, r := range ranges {
    if last+1 < r[0] {
      ans = append(ans, []int{last + 1, r[0] - 1})
    }
    last = max(last, r[1])
  }
  if last+1 < n {
    ans = append(ans, []int{last + 1, n - 1})
  }
  return
}