1893. Check if All the Integers in a Range Are Covered
Description
You are given a 2D integer array ranges
and two integers left
and right
. Each ranges[i] = [starti, endi]
represents an inclusive interval between starti
and endi
.
Return true
if each integer in the inclusive range [left, right]
is covered by at least one interval in ranges
. Return false
otherwise.
An integer x
is covered by an interval ranges[i] = [starti, endi]
if starti <= x <= endi
.
Example 1:
Input: ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5 Output: true Explanation: Every integer between 2 and 5 is covered: - 2 is covered by the first range. - 3 and 4 are covered by the second range. - 5 is covered by the third range.
Example 2:
Input: ranges = [[1,10],[10,20]], left = 21, right = 21 Output: false Explanation: 21 is not covered by any range.
Constraints:
1 <= ranges.length <= 50
1 <= starti <= endi <= 50
1 <= left <= right <= 50
Solutions
Solution 1: Difference Array
We can use the idea of a difference array to create a difference array $\textit{diff}$ of length $52$.
Next, we iterate through the array $\textit{ranges}$. For each interval $[l, r]$, we increment $\textit{diff}[l]$ by $1$ and decrement $\textit{diff}[r + 1]$ by $1$.
Then, we iterate through the difference array $\textit{diff}$, maintaining a prefix sum $s$. For each position $i$, we increment $s$ by $\textit{diff}[i]$. If $s \le 0$ and $left \le i \le right$, it indicates that an integer $i$ within the interval $[left, right]$ is not covered, and we return $\textit{false}$.
If we finish iterating through the difference array $\textit{diff}$ without returning $\textit{false}$, it means that every integer within the interval $[left, right]$ is covered by at least one interval in $\textit{ranges}$, and we return $\textit{true}$.
The time complexity is $O(n + M)$, and the space complexity is $O(M)$. Here, $n$ is the length of the array $\textit{ranges}$, and $M$ is the maximum value of the interval, which in this case is $M \le 50$.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1< |