Skip to content

2655. Find Maximal Uncovered Ranges πŸ”’

Description

You are given an integer n which is the length of a 0-indexed array nums, and a 0-indexed 2D-array ranges, which is a list of sub-ranges of nums (sub-ranges may overlap).

Each row ranges[i] has exactly 2 cells:

  • ranges[i][0], which shows the start of the ith range (inclusive)
  • ranges[i][1], which shows the end of the ith range (inclusive)

These ranges cover some cells of nums and leave some cells uncovered. Your task is to find all of the uncovered ranges with maximal length.

Return a 2D-array answer of the uncovered ranges, sorted by the starting point in ascending order.

By all of the uncovered ranges with maximal length, we mean satisfying two conditions:

  • Each uncovered cell should belong to exactly one sub-range
  • There should not exist two ranges (l1, r1) and (l2, r2) such that r1 + 1 = l2

 

Example 1:

Input: n = 10, ranges = [[3,5],[7,8]]
Output: [[0,2],[6,6],[9,9]]
Explanation: The ranges (3, 5) and (7, 8) are covered, so if we simplify the array nums to a binary array where 0 shows an uncovered cell and 1 shows a covered cell, the array becomes [0,0,0,1,1,1,0,1,1,0] in which we can observe that the ranges (0, 2), (6, 6) and (9, 9) aren't covered.

Example 2:

Input: n = 3, ranges = [[0,2]]
Output: []
Explanation: In this example, the whole of the array nums is covered and there are no uncovered cells so the output is an empty array.

Example 3:

Input: n = 7, ranges = [[2,4],[0,3]]
Output: [[5,6]]
Explanation: The ranges (0, 3) and (2, 4) are covered, so if we simplify the array nums to a binary array where 0 shows an uncovered cell and 1 shows a covered cell, the array becomes [1,1,1,1,1,0,0] in which we can observe that the range (5, 6) is uncovered.

 

Constraints:

  • 1 <= n <= 109
  • 0 <= ranges.length <= 106
  • ranges[i].length = 2
  • 0 <= ranges[i][j] <= n - 1
  • ranges[i][0] <= ranges[i][1]

Solutions

Solution 1: Sorting

We sort all intervals by their left endpoints in ascending order, then traverse all intervals from left to right, maintaining a variable \(\textit{last}\) to represent the rightmost endpoint that has been covered so far, initially \(\textit{last}=-1\).

If the left endpoint of the current interval is greater than \(\textit{last}+1\), it means \([\textit{last}+1, l-1]\) is an uncovered interval, and we add it to the answer array. Then we update \(\textit{last}\) to the right endpoint of the current interval and continue traversing the next interval. After traversing all intervals, if \(\textit{last}+1 < n\), it means \([\textit{last}+1, n-1]\) is an uncovered interval, and we add it to the answer array.

Finally, we return the answer array.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\), where \(n\) is the length of the array \(\textit{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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function findMaximalUncoveredRanges(n: number, ranges: number[][]): number[][] {
    ranges.sort((a, b) => a[0] - b[0]);
    let last = -1;
    const ans: number[][] = [];
    for (const [l, r] of ranges) {
        if (last + 1 < l) {
            ans.push([last + 1, l - 1]);
        }
        last = Math.max(last, r);
    }
    if (last + 1 < n) {
        ans.push([last + 1, n - 1]);
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
impl Solution {
    pub fn find_maximal_uncovered_ranges(n: i32, mut ranges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        ranges.sort_by_key(|x| x[0]);
        let mut last = -1;
        let mut ans = Vec::new();
        for range in ranges {
            let l = range[0];
            let r = range[1];
            if last + 1 < l {
                ans.push(vec![last + 1, l - 1]);
            }
            last = last.max(r);
        }
        if last + 1 < n {
            ans.push(vec![last + 1, n - 1]);
        }
        ans
    }
}

Comments