This article is participating in Python Theme Month. See the link to the event for more details
Topic describes
This is 1893 on LeetCode. Check whether all integers in the region are overwritten, difficulty is easy.
Tag: “simulation”, “tree array”, “segment tree”
Give you a two-dimensional array of integers ranges and two integers left and right. Each ranges[I] = [start, endi] represents a closed range from start to endi.
Return true if every integer in the closed interval [left, right] is covered by at least one of ranges, otherwise return false.
Given that the interval ranges[I] = [start, endi], if the integer x satisfies start <= x <= endi, then we say that the integer x is covered.
Example 1:
Input: ranges = [[1,2],[3,4],[5,6], left = 2, right = 5 output: true explanation: every integer from 2 to 5 is covered: -2 is covered by the first interval. Minus 3 and 4 are covered by the second interval. Minus 5 is covered by the third interval.Copy the codeExample 2:
Input: ranges = [[1,10],[10,20]], left = 21, right = 21 output: false description: 21 is not covered by any range.Copy the codeTip:
- 1 <= ranges.length <= 50
- 1 <= starti <= endi <= 50
- 1 <= left <= right <= 50
simulation
A simple idea is to simulate the meaning of the question by checking every integer in [left,right][left, right][left,right], and if an integer is not covered by the closed range in Rangesrangesranges, Return False directly, and return True if all values pass the check.
Code:
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; }}Copy the codePython 3 code:
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
Copy the code- Time complexity: let the number of integers between [left,right][left, right][left,right] [left,right] be NNN, and the length of rangesrangesranges be MMM. The global complexity is O(n∗m)O(n * m)O(n∗m)
- Space complexity: O(1)O(1)O(1)
Tree array
[A] difficult [B] difficult [C] difficult [D] difficult
[left,right][left, right][left,right] [left,right][left, right][left,right] Each querys querys [I] [I] querys [I] contains four indexes (a, b, l, r) (a, b, l, r) (a, b, l, r) : The representative asks if each number in [L,r][L,r][L,r] is covered by the closed interval of [a,b][a, b][a,b] in rangerangerange.
To do this, we need to use a “persistent tree array” or a “chairman tree” in conjunction with the exclusion principle.
The basic idea is to use the count of range[0,b]range[0,b]range[0,b] minus the count of range[0,a−1]range[0, a-1]range[0,a−1] to get the count of [a,b][a, b].
Since the data range is small, only 505050, we can use “tree array” to solve the problem:
void add(int x, int u): For numerical values
Occurrence times
Operation;int query(int x): Queries a satisfaction
The number of values of.
So obviously, if we need to query whether a number XXX occurs, we can know it by querying CNT =query(x)−query(x−1) CNT =query(x) -query (x-1) CNT =query(x)− Query (x−1).
Java code:
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; }}Copy the codePython 3 code:
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
Copy the code- Time complexity: Let the number of integers between [left,right][left, right][left,right] be NNN, ∑ I =0range.legth−1ranges[I].length\sum_{I =0}^{range.legth – 1}ranges[I].length\sum_{I =0}^{range.legth – 1}ranges[I].length =0range.legth−1ranges[I].length = Sumsumsum: the constant CCC is 555555. The construction complexity is O(sumlogC)O(sum\log C)O(sumlogC), and the query complexity is O(nlogC)O(n\log{C})O(nlogC). O(sumlogC+nlogC)O(sum\log{C} +n \log{C})O(sumlogC+nlogC)
- Space complexity: O(C)O(C)O(C) O(C)
Tree arrays (de-optimized)
In the naive “tree array” solution, we cannot directly query the number of overwrites in the interval [l,r][l, r][l,r] because “a value may be repeatedly added to the tree array”.
Therefore, a better approach is to: When I add a tree to the tree array, Then CNT = Query (r)− Query (L −1) CNT =query(r) -query (L-1) CNT =query(r)− Query (L −1) CNT = Query (r)− Query (L −1) CNT = Query (r)− Query (L −1)
Such Set removals reduce the complexity of our query from O(nlogC)O(n\log{C})O(nlogC) to O(logC)O(\log{C})O(logC).
Given the small range of values, it is natural to use an array instead of a Set (see P2)
Java code:
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);
returntot == cnt; }}Copy the codeJava code:
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);
returntot == cnt; }}Copy the code- Time complexity: Let the number of integers between [left,right][left, right][left,right] be NNN, ∑ I =0range.legth−1ranges[I].length\sum_{I =0}^{range.legth – 1}ranges[I].length\sum_{I =0}^{range.legth – 1}ranges[I].length =0range.legth−1ranges[I].length = Sumsumsum: the constant CCC is 555555. O(sumlogC)O(sum\log C)O(sumlogC), and O(logC)O(\log{C})O(logC). O(sumlogC+logC)O(sum\log{C} + \log{C})O(sumlogC+logC)
- Space complexity: O(C+∑ I =0range.legth−1ranges[I].length)O(C + \sum_{I =0}^{range.legth – 1} ranges [I]. Length) O (C + ∑ I = 0 range. The legth – 1 ranges [I] length)
Line segment tree (excluding “lazy mark”)
A more advanced approach is to use a “segment tree”, which, like the “tree array (optimization)” solution, can also be used with persistence to solve “online” problems.
Unlike the tree array, which mainly solves the “single point modification & interval query”, the line segment tree can solve the vast majority of “interval modification (interval modification/single point modification) & interval query” problems.
For this problem, because the data range is only 555555, so we can use the same idea as the “tree array (optimization)” solution, to achieve a line segment tree without “lazy tag” to do (only support single-point modification & interval query).
Java code:
class Solution {
// Represents the number of CNT covered in the interval [L, r]
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); }}// Start with the subscript u of the tr array and mark at the value 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); }}// Query how many values are marked in the range [l,r], starting with the subscript u of tr
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);
returntot == cnt; }}Copy the codePython 3 code:
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)
ifl ! = 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)
# mark the value x starting with the subscript u of tr array
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)
[l,r] [l,r] [l,r] [l,r] [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
Copy the code- Time complexity: Let the number of integers between [left,right][left, right][left,right] be NNN, ∑ I =0range.legth−1ranges[I].length\sum_{I =0}^{range.legth – 1}ranges[I].length\sum_{I =0}^{range.legth – 1}ranges[I].length =0range.legth−1ranges[I].length = Sumsumsum: the constant CCC is 555555. O(sumlogC)O(sum\log C)O(sumlogC), and O(logC)O(\log{C})O(logC). O(sumlogC+logC)O(sum\log{C} + \log{C})O(sumlogC+logC)
- Space complexity: O(C∗4)O(C * 4)O(C∗4)
The last
This is the number 1893 article in our “Brush through LeetCode” series, which began on 2021/01/01. By the start date, there are 1916 questions on LeetCode, some of which are locked. We will first brush through all the questions without locks.
In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.
In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .
In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.