Check if All the Integers in a Range Are Covered
Problem
You are given a list of inclusive intervals ranges, where each [start, end] covers every integer from start to end. Given two integers left and right, return true if every integer in the inclusive range [left, right] is covered by at least one interval, and false otherwise.
ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5truedef is_covered(ranges, left, right):
diff = [0] * 52
for s, e in ranges:
diff[s] += 1
diff[e + 1] -= 1
cur = 0
for i in range(52):
cur += diff[i]
if left <= i <= right and cur <= 0:
return False
return Truefunction isCovered(ranges, left, right) {
const diff = new Array(52).fill(0);
for (const [s, e] of ranges) {
diff[s] += 1;
diff[e + 1] -= 1;
}
let cur = 0;
for (let i = 0; i < 52; i++) {
cur += diff[i];
if (i >= left && i <= right && cur <= 0) return false;
}
return true;
}class Solution {
public boolean isCovered(int[][] ranges, int left, int right) {
int[] diff = new int[52];
for (int[] r : ranges) {
diff[r[0]] += 1;
diff[r[1] + 1] -= 1;
}
int cur = 0;
for (int i = 0; i < 52; i++) {
cur += diff[i];
if (i >= left && i <= right && cur <= 0) return false;
}
return true;
}
}bool isCovered(vector<vector<int>>& ranges, int left, int right) {
vector<int> diff(52, 0);
for (auto& r : ranges) {
diff[r[0]] += 1;
diff[r[1] + 1] -= 1;
}
int cur = 0;
for (int i = 0; i < 52; i++) {
cur += diff[i];
if (i >= left && i <= right && cur <= 0) return false;
}
return true;
}Explanation
The brute-force idea is to walk every integer from left to right and, for each one, scan all the intervals to see if it is covered. That works but re-scans the same intervals over and over. The clever trick here is the difference array: we record where coverage turns on and off, then read off how many intervals cover each point with a single prefix-sum sweep.
Because the constraints keep all values small (between 1 and 50), we use a fixed diff array of size 52. For each interval [s, e] we do diff[s] += 1 ("one more interval starts covering here") and diff[e + 1] -= 1 ("that interval stops covering right after e"). Each interval costs just two operations, no matter how wide it is.
Now we sweep from index 0 upward, keeping a running total cur. At index i, cur += diff[i] equals the number of intervals that cover i. If i sits inside our target window [left, right] and cur has dropped to zero, then this integer is uncovered, so we can immediately return false.
Example: ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5. The marks give diff[1]+=1, diff[3]-=1; diff[3]+=1, diff[5]-=1; diff[5]+=1, diff[7]-=1. Sweeping, the coverage count is 1 at every index from 1 to 6, so positions 2, 3, 4, 5 are all covered and the answer is true.
If instead the intervals left a gap inside [left, right], the running count would touch zero there and we would catch it on the spot. Every step is constant work, so the whole check is fast.