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
};