Skip to content

2655. Find Maximal Uncovered Ranges 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  vector<vector<int>> findMaximalUncoveredRanges(int n,
                                                 vector<vector<int>>& ranges) {
    vector<vector<int>> ans;
    int start = 0;

    ranges::sort(ranges);

    for (const vector<int>& range : ranges) {
      const int l = range[0];
      const int r = range[1];
      if (start < l)
        ans.push_back({start, l - 1});
      if (start <= r)
        start = r + 1;
    }

    if (start < n)
      ans.push_back({start, n - 1});

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int[][] findMaximalUncoveredRanges(int n, int[][] ranges) {
    List<int[]> ans = new ArrayList<>();
    int start = 0;

    Arrays.sort(ranges, (a, b) -> a[0] - b[0]);

    for (int[] range : ranges) {
      final int l = range[0];
      final int r = range[1];
      if (start < l)
        ans.add(new int[] {start, l - 1});
      if (start <= r)
        start = r + 1;
    }

    if (start < n)
      ans.add(new int[] {start, n - 1});

    return ans.stream().toArray(int[][] ::new);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:
    ans = []
    start = 0

    for l, r in sorted(ranges):
      if start < l:
        ans.append([start, l - 1])
      if start <= r:
        start = r + 1

    if start < n:
      ans.append([start, n - 1])

    return ans