题目描述
这是 LeetCode 上的 1893. 检查是否区域内所有整数都被覆盖 ，难度为 简单。
Tag : 「模拟」、「树状数组」、「线段树」
给你一个二维整数数组 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][left,right] 中的每个整数，如果检查过程中发现某个整数没被 rangesranges 中的闭区间所覆盖，那么直接返回 False，所有数值通过检查则返回 True。
代码：
class Solution { public boolean isCovered(int[][] rs, int l, int r) { for (int i = l; i <= r; i++) { boolean ok = false; for (int[] cur : rs) { int a = cur[0], b = cur[1]; if (a <= i && i <= b) { ok = true; break; } } if (!ok) return false; } return true; } } 复制代码
Python 3 代码：
class Solution: def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool: for i in range(left, right+1): ok = False for a, b in ranges: if a <= i <= b: ok = True break if not ok: return False return True 复制代码
- 时间复杂度：令 [left, right][left,right] 之间整数数量为 nn，rangesranges 长度为 mm。整体复杂度为 O(n * m)O(n∗m)
- 空间复杂度：O(1)O(1)
树状数组
针对此题，可以有一个很有意思的拓展，将本题难度提升到【中等】甚至是【困难】。
将查询 [left, right][left,right] 修改为「四元查询数组」querysquerys，每个 querys[i]querys[i] 包含四个指标 (a,b,l,r)(a,b,l,r)：代表询问 [l, r][l,r] 中的每个数是否在 rangerange 中 [a, b][a,b] 的闭区间所覆盖过。
如果进行这样的拓展的话，那么我们需要使用「持久化树状数组」或者「主席树」来配合「容斥原理」来做。
基本思想都是使用 range[0,b]range[0,b] 的计数情况减去 range[0, a-1]range[0,a−1] 的计数情况来得出 [a, b][a,b] 的计数情况。
回到本题，由于数据范围很小，只有 5050，我们可以使用「树状数组」进行求解：
void add(int x, int u)：对于数值 xx 出现次数进行 +u+u 操作；int query(int x)：查询某个满足 <= x<=x 的数值的个数。
那么显然，如果我们需要查询一个数值 xx 是否出现过，可以通过查询 cnt = query(x) - query(x - 1)cnt=query(x)−query(x−1) 来得知。
Java 代码：
class Solution { int n = 55; int[] tr = new int[n]; int lowbit(int x) { return x & -x; } void add(int x, int u) { for (int i = x; i <= n; i += lowbit(i)) tr[i] += u; } int query(int x) { int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i]; return ans; } public boolean isCovered(int[][] rs, int l, int r) { for (int[] cur : rs) { int a = cur[0], b = cur[1]; for (int i = a; i <= b; i++) { add(i, 1); } } for (int i = l; i <= r; i++) { int cnt = query(i) - query(i - 1); if (cnt == 0) return false; } return true; } } 复制代码
Python 3 代码：
class Solution: def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool: n = 55 tr = [0] * n def lowbit(x): return x & -x def add(x, u): i = x while i <= n: tr[i] += u i += lowbit(i) def query(x): ans = 0 i = x while i > 0: ans += tr[i] i -= lowbit(i) return ans for a,b in ranges: for i in range(a, b+1): add(i, 1) for i in range(left, right+1): cnt = query(i) - query(i-1) if not cnt: return False return True 复制代码
- 时间复杂度：令 [left, right][left,right] 之间整数数量为 nn，\sum_{i = 0}^{range.legth - 1}ranges[i].length∑i=0range.legth−1ranges[i].length 为 sumsum，常数 CC 固定为 5555。建树复杂度为 O(sum\log C)O(sumlogC)，查询查询复杂度为 O(n\log{C})O(nlogC)。整体复杂度为 O(sum\log{C} + n\log{C})O(sumlogC+nlogC)
- 空间复杂度：O(C)O(C)
树状数组（去重优化）
在朴素的「树状数组」解法中，我们无法直接查询 [l, r][l,r] 区间中被覆盖过的个数的根本原因是「某个值可能会被重复添加到树状数组中」。
因此，一种更加优秀的做法：在往树状数组中添树的时候进行去重，然后通过 cnt = query(r) - query(l - 1)cnt=query(r)−query(l−1) 直接得出 [l, r][l,r] 范围内有多少个数被添加过。
这样的 Set 去重操作可以使得我们查询的复杂度从 O(n\log{C})O(nlogC) 下降到 O(\log{C})O(logC)。
由于数值范围很小，自然也能够使用数组来代替
Set进行标记（见 P2）
Java 代码：
class Solution { int n = 55; int[] tr = new int[n]; int lowbit(int x) { return x & -x; } void add(int x, int u) { for (int i = x; i <= n; i += lowbit(i)) tr[i] += u; } int query(int x) { int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i]; return ans; } public boolean isCovered(int[][] rs, int l, int r) { Set<Integer> set = new HashSet<>(); for (int[] cur : rs) { int a = cur[0], b = cur[1]; for (int i = a; i <= b; i++) { if (!set.contains(i)) { add(i, 1); set.add(i); } } } int tot = r - l + 1, cnt = query(r) - query(l - 1); return tot == cnt; } } 复制代码
Java 代码：
class Solution { int n = 55; int[] tr = new int[n]; boolean[] vis = new boolean[n]; int lowbit(int x) { return x & -x; } void add(int x, int u) { for (int i = x; i <= n; i += lowbit(i)) tr[i] += u; } int query(int x) { int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i]; return ans; } public boolean isCovered(int[][] rs, int l, int r) { for (int[] cur : rs) { int a = cur[0], b = cur[1]; for (int i = a; i <= b; i++) { if (!vis[i]) { add(i, 1); vis[i] = true; } } } int tot = r - l + 1, cnt = query(r) - query(l - 1); return tot == cnt; } } 复制代码
- 时间复杂度：令 [left, right][left,right] 之间整数数量为 nn，\sum_{i = 0}^{range.legth - 1}ranges[i].length∑i=0range.legth−1ranges[i].length 为 sumsum，常数 CC 固定为 5555。建树复杂度为 O(sum\log C)O(sumlogC)，查询查询复杂度为 O(\log{C})O(logC)。整体复杂度为 O(sum\log{C} + \log{C})O(sumlogC+logC)
- 空间复杂度：O(C + \sum_{i = 0}^{range.legth - 1}ranges[i].length)O(C+∑i=0range.legth−1ranges[i].length)
线段树（不含“懒标记”）
更加进阶的做法是使用「线段树」来做，与「树状数组（优化）」解法一样，线段树配合持久化也可以用于求解「在线」问题。
与主要解决「单点修改 & 区间查询」的树状数组不同，线段树能够解决绝大多数「区间修改（区间修改/单点修改）& 区间查询」问题。
对于本题，由于数据范围只有 5555，因此我们可以使用与「树状数组（优化）」解法相同的思路，实现一个不包含“懒标记”的线段树来做（仅支持单点修改 & 区间查询）。
Java 代码：
class Solution { // 代表 [l, r] 区间有 cnt 个数被覆盖 class Node { int l, r, cnt; Node (int _l, int _r, int _cnt) { l = _l; r = _r; cnt = _cnt; } } int N = 55; Node[] tr = new Node[N * 4]; void pushup(int u) { tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt; } void build(int u, int l, int r) { if (l == r) { tr[u] = new Node(l, r, 0); } else { tr[u] = new Node(l, r, 0); int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(u); } } // 从 tr 数组的下标 u 开始，在数值 x 的位置进行标记 void update(int u, int x) { if (tr[u].l == x && tr[u].r == x) { tr[u].cnt = 1; } else { int mid = tr[u].l + tr[u].r >> 1; if (x <= mid) update(u << 1, x); else update(u << 1 | 1, x); pushup(u); } } // 从 tr 数组的下标 u 开始，查询 [l,r] 范围内有多少个数值被标记 int query(int u, int l, int r) { if (l <= tr[u].l && tr[u].r <= r) return tr[u].cnt; int mid = tr[u].l + tr[u].r >> 1; int ans = 0; if (l <= mid) ans += query(u << 1, l, r); if (r > mid) ans += query(u << 1 | 1, l, r); return ans; } public boolean isCovered(int[][] rs, int l, int r) { build(1, 1, N); for (int[] cur : rs) { int a = cur[0], b = cur[1]; for (int i = a; i <= b; i++) { update(1, i); } } int tot = r - l + 1 , cnt = query(1, l, r); return tot == cnt; } } 复制代码
Python 3 代码：
class Solution: def isCovered(self, ranges: List[List[int]], l: int, r: int) -> bool: def pushup(u): tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt def build(u, l, r): tr[u] = Node(l, r, 0) if l != r: tr[u] = Node(l, r, 0) mid = l + r >> 1 build(u << 1, l, mid) build(u << 1 | 1, mid + 1, r) pushup(u) # 从 tr 数组的下标 u 开始，在数值 x 的位置进行标记 def update(u, x): if tr[u].l == x and tr[u].r == x: tr[u].cnt = 1 else: mid = tr[u].l + tr[u].r >> 1 if x <= mid: update(u << 1, x) else: update(u << 1 | 1, x) pushup(u) # 从 tr 数组的下标 u 开始，查询 [l,r] 范围内有多少个数值被标记 def query(u, l, r): if l <= tr[u].l and tr[u].r <= r: return tr[u].cnt mid = tr[u].l + tr[u].r >> 1 ans = 0 if l <= mid: ans += query(u << 1, l, r) if r > mid: ans += query(u << 1 | 1, l, r) return ans N = 55 tr = [None] * N * 4 build(1, 1, N) for a,b in ranges: for i in range(a, b+1): update(1, i) tot = r - l + 1 cnt = query(1, l, r) return tot == cnt class Node: def __init__(self, l, r, cnt): self.l = l self.r = r self.cnt = cnt 复制代码
- 时间复杂度：令 [left, right][left,right] 之间整数数量为 nn，\sum_{i = 0}^{range.legth - 1}ranges[i].length∑i=0range.legth−1ranges[i].length 为 sumsum，常数 CC 固定为 5555。建树复杂度为 O(sum\log C)O(sumlogC)，查询查询复杂度为 O(\log{C})O(logC)。整体复杂度为 O(sum\log{C} + \log{C})O(sumlogC+logC)
- 空间复杂度：O(C * 4)O(C∗4)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1893 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
