跳转至

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

题目描述

现给你一个长度为 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\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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][]);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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
}

评论