1893. 检查是否区域内所有整数都被覆盖
1893. 检查是否区域内所有整数都被覆盖
题目
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
题目大意
给你一个二维整数数组 ranges
和两个整数 left
和 right
。每个 ranges[i] = [starti, endi]
表示一个从 starti
到 endi
的 闭区间 。
如果闭区间 [left, right]
内每个整数都被 ranges
中 至少一个 区间覆盖,那么请你返回 true
,否则返回 false
。
已知区间 ranges[i] = [starti, endi]
,如果整数 x
满足 starti <= x <= endi
,那么我们称整数x
被覆盖了。
示例 1:
输入: ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
输出: true
解释: 2 到 5 的每个整数都被覆盖了:
- 2 被第一个区间覆盖。
- 3 和 4 被第二个区间覆盖。
- 5 被第三个区间覆盖。
示例 2:
输入: ranges = [[1,10],[10,20]], left = 21, right = 21
输出: false
解释: 21 没有被任何一个区间覆盖。
提示:
1 <= ranges.length <= 50
1 <= starti <= endi <= 50
1 <= left <= right <= 50
解题思路
解题思路
差分数组是一种用来高效处理区间更新的方法。通过在区间的起始和结束位置进行标记,然后在最终结果中进行累加得到每个位置的实际值。
我们可以利用差分数组来标记每个区间的覆盖范围,然后最终检查目标区间 [left, right]
是否完全被覆盖。
初始化差分数组:
- 创建一个足够大的差分数组
arr
,它的大小为 52,足以容纳从0
到50
的位置,所有位置初始化为0
。
- 创建一个足够大的差分数组
更新差分数组:对于每个给定的区间
[start, end]
:- 将
arr[start]
增加 1,表示从start
位置开始有覆盖。 - 将
arr[end + 1]
减去 1,表示从end + 1
位置开始没有覆盖。
- 将
检查区间
[left, right]
是否完全被覆盖:- 使用一个
cur
变量来累加arr
数组的值,表示当前位置的覆盖状态。 - 遍历
arr
数组的从1
到right
范围,检查每个位置的覆盖状态。如果发现某个位置没有被覆盖,返回false
。 - 如果所有位置都被覆盖,则返回
true
。
- 使用一个
复杂度分析
- 时间复杂度:
O(n)
,其中n
是区间ranges
的长度,- 更新差分数组需要遍历每个给定区间的起始和结束位置,时间复杂度为
O(n)
。 - 遍历差分数组进行区间检查,最大只需要遍历 52 个元素,时间复杂度为
O(1)
(常数时间)。
- 更新差分数组需要遍历每个给定区间的起始和结束位置,时间复杂度为
- 空间复杂度:
O(1)
,使用了一个大小为 52 的数组arr
来存储差分标记,即常数空间。
代码
/**
* @param {number[][]} ranges
* @param {number} left
* @param {number} right
* @return {boolean}
*/
var isCovered = function (ranges, left, right) {
let arr = new Array(52).fill(0);
for (let [start, end] of ranges) {
arr[start]++;
arr[end + 1]--;
}
let cur = 0;
for (let i = 1; i <= right; i++) {
cur += arr[i];
if (i >= left && cur < 1) {
return false;
}
}
return true;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
2655 | 寻找最大长度的未覆盖区间 🔒 | 数组 排序 | 🟠 | 🀄️ 🔗 |