How can I optimize the brute-force solution for checking range coverage?

You can use hash tables or a prefix sum approach to avoid checking every integer in the range individually, which reduces the time complexity.

What is the main pattern in the 'Check if All the Integers in a Range Are Covered' problem?

The main pattern is array scanning plus hash lookup, which involves checking if each integer in the target range is covered by any given interval.

What are the constraints of the 'Check if All the Integers in a Range Are Covered' problem?

The constraints are that the number of ranges is between 1 and 50, each range has start and end values between 1 and 50, and the range [left, right] is also between 1 and 50.

Can the solution for this problem be optimized further?

Yes, the solution can be optimized by using hash tables or prefix sum arrays to track the coverage efficiently.

What is the time complexity of the brute-force solution for this problem?

The time complexity of the brute-force solution is O(n*m), where n is the number of ranges and m is the size of the range [left, right].

#1893

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个二维整数数组 ranges 和两个整数 left 和 right 。每个 ranges[i] = [start i , end i ] 表示一个从 start i 到 end i 的闭区间。如果闭区间 [left, right] 内每个整数都被 ranges 中至少一个区间覆盖，那…

数组哈希表前缀和

题目描述

给你一个二维整数数组 ranges 和两个整数 left 和 right 。每个 ranges[i] = [start_i, end_i] 表示一个从 start_i 到 end_i 的 闭区间 。

如果闭区间 [left, right] 内每个整数都被 ranges 中 至少一个 区间覆盖，那么请你返回 true ，否则返回 false 。

已知区间 ranges[i] = [start_i, end_i] ，如果整数 x 满足 start_i <= x <= end_i ，那么我们称整数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 <= start_i <= end_i <= 50
1 <= left <= right <= 50

lightbulb

解题思路

方法一：差分数组

我们可以使用差分数组的思想，创建一个长度为 $52$ 的差分数组 $\textit{diff}$ 。

接下来，我们遍历数组 $\textit{ranges}$ ，对于每个区间 $[l, r]$ ，我们令 $\textit{diff}[l]$ 自增 $1$ ，而 $\textit{diff}[r + 1]$ 自减 $1$ 。

接着，我们遍历差分数组 $\textit{diff}$ ，维护一个前缀和 $s$ ，对于每个位置 $i$ ，我们令 $s$ 自增 $\textit{diff}[i]$ ，如果 $s \le 0$ 且 $left \le i \le right$ ，则说明区间 $[left, right]$ 中有一个整数 $i$ 没有被覆盖，返回 $\textit{false}$ 。

如果遍历完差分数组 $\textit{diff}$ 后都没有返回 $\textit{false}$ ，则说明区间 $[left, right]$ 中的每个整数都被 $\textit{ranges}$ 中至少一个区间覆盖，返回 $\textit{true}$ 。

时间复杂度 $O(n + M)$ ，空间复杂度 $O(M)$ 。其中 $n$ 是数组 $\textit{ranges}$ 的长度，而 $M$ 是区间的最大值，本题中 $M \le 50$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
        diff = [0] * 52
        for l, r in ranges:
            diff[l] += 1
            diff[r + 1] -= 1
        s = 0
        for i, x in enumerate(diff):
            s += x
            if s <= 0 and left <= i <= right:
                return False
        return True

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate shows understanding of array iteration techniques.
question_mark
The candidate demonstrates awareness of optimizing brute-force solutions.
question_mark
The candidate considers the use of advanced data structures for improving performance.

warning

常见陷阱

外企场景

error
Overcomplicating the solution with unnecessary data structures for small inputs.
error
Forgetting to check coverage for every integer between left and right.
error
Confusing inclusive and exclusive range bounds when verifying coverage.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the intervals can overlap?
arrow_right_alt
How would you approach the problem if the range size was very large?
arrow_right_alt
Can the solution be optimized if ranges are sorted?

help

常见问题

外企场景

继续练习

#1943 描述绘画结果 #2025 分割数组的最多方案数 #1674 使数组互补的最少操作次数