Find Maximal Uncovered Ranges
Problem statement
For this exercise, consider every integer position from 0 through n - 1. Each row [start, end] in covered covers both endpoints and every integer between them. Rows may be unordered, overlap, repeat or touch.
Return all maximal uncovered integer ranges as inclusive pairs, ordered by increasing start. A returned range must contain only uncovered positions and cannot be extended left or right inside the domain without meeting a covered position. Return an empty list if every position is covered.
Function
uncoveredRanges(n: int, covered: int[][]) → int[][]Examples
Example 1
n = 8covered = [[1,2],[4,5]]return = [[0,0],[3,3],[6,7]]The uncovered positions are 0, 3, 6 and 7. The last two are adjacent, so the maximal ranges are [0,0], [3,3] and [6,7].
Example 2
n = 6covered = [[0,5],[2,3]]return = []The first row already covers every position from 0 to 5. The nested row does not create any uncovered position, so the result is empty.
Constraints
- 1 <= n <= 10^9
- 0 <= covered.length <= 2000
- Every covered row has exactly 2 integers.
- 0 <= covered[i][j] <= 999999999
- Every row satisfies 0 <= start <= end < n.