1893. 检查是否区域内所有整数都被覆盖

1893. 检查是否区域内所有整数都被覆盖

拿到没想到什么好方法,先暴力解

1
2
3
4
5
6
7
8
9
10
11
12
13
var isCovered = function(ranges, left, right) {
for(let i = left ; i <= right ; i ++) {
let include = false
for(let index = 0 ; index < ranges.length ; index ++) {
let [start,end] = ranges[index]
if (i >=start && i <=end) {
include = true
}
}
if (!include) return false
}
return true
};

思考优化,可以通过start ,end ,当 start <= left 时, [left … end] 集合已经包含在内了,继续压缩 [end + 1 , right ] 直到集合里面没有元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var isCovered = function(ranges, left, right) {
ranges = ranges.sort((a,b) => a - b)
for(let i = 0 ; i < ranges.length;i++) {
let [start,end] = ranges[i];
// 根据范围收缩左边界
if (start <= left) {
left = Math.max(end,right)
}
if (left >= right) {
return true
}
}
return left >= right
};