1893. 检查是否区域内所有整数都被覆盖 Check if All the Integers in a Range Are Covered

问题描述

这个问题有两个思路可以处理.

集合 Set

使用集合来存储区间上的每个点.

步骤如下:

1. 创建集合
2. 遍历 ranges 数组, 将每个范围上的所有点位都存储到集合中
3. 遍历 [left..=right] 区间上的所有点位, 查看它们是否都在集合中

#![allow(unused)]
fn main() {
use std::collections::HashSet;

// Hashset
pub fn is_covered1(ranges: Vec<Vec<i32>>, left: i32, right: i32) -> bool {
    // 将所有的点位存储到集合中
    let mut set = HashSet::new();
    for range in ranges {
        for i in range[0]..=range[1] {
            set.insert(i);
        }
    }

    // 遍历区间 [left..=right] 上的所有点, 查看它们是否都在集合中
    for i in left..=right {
        if !set.contains(&i) {
            return false;
        }
    }
    true
}
}

该算法:

• 时间复杂度是 O(n m), 其中 n 是范围的个数, 而 m 是最大的范围区间
• 空间复杂度是 O(n), 其中 n 是范围包含的所有点位个数

合并区间 Merge intervals

这个方法用于计算区间重叠很方便.

其步骤如下:

1. 先对 ranges 数组进行排序, 依照范围的起始点
2. 构造合并区间 intervals
   1. 初始化区间值 start = 0, end = 0
   2. 遍历 ranges, 并判断当前区间是否能跟区间值 [start..=end] 拼接在一起, 判定条件是 range[0] <= end + 1
   3. 如果可以, 就只需要移动区间的终点值, end = end.max(range[1])
   4. 如果不行, 就先将当前区间 [start..=end] 加入到 intervals, 然后更新 [start..=end] 区间
3. 查找 [left..=right] 区间是否在 intervals 内

#![allow(unused)]
fn main() {
// Merge intervals
pub fn is_covered2(ranges: Vec<Vec<i32>>, left: i32, right: i32) -> bool {
    // 依照起始点对区间进行排序
    let mut ranges = ranges;
    ranges.sort_unstable_by_key(|range| range[0]);

    // 合并区间
    let mut intervals = Vec::new();
    let mut start = 0;
    let mut end = 0;
    for range in ranges {
        if range[0] > end + 1 {
            // 区间无法拼接在一起
            if start <= end {
                intervals.push((start, end));
            }
            start = range[0];
            end = range[1];
        } else {
            // 区间可以拼接在一起
            end = end.max(range[1]);
        }
    }
    if start <= end {
        intervals.push((start, end));
    }

    // 查找区间是否有包含
    // 可以使用二分法查找
    for interval in intervals {
        if interval.0 <= left && right <= interval.1 {
            return true;
        }
    }
    false
}
}

该算法:

• 时间复杂度是 O(n log(n)), n 是 ranges 中的区间个数
• 空间复杂度是 O(n), n 是 ranges 内不连接的区间个数