Make writing a habit together! This is the 12th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Topic describes

This is 1893 on LeetCode. Check if all integers in the area are covered, difficulty is simple.

Tag: “simulation”, “tree array”, “line tree”

I give you a two dimensional array of integers ranges and two integers left and right. Ranges [I]=[starti,endi]ranges[I]=[start_i, End_i]ranges[I]=[starti,endi] indicates a closed range from startistart_istarti to endiend_iendi.

Return true if every integer in the closed range [left,right][left, right] is covered by at least one of the ranges, otherwise return false.

Ranges [I]=[starti,endi]ranges[I]=[start_i, end_I]ranges[I]=[starti,endi], If the integer x satisfies starti<=x<=endistart_i <=x<= end_istarti<=x<=endi, then the integer x is said to be 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 range. Minus 3 and 4 are covered by the second interval. Minus 5 is covered by the third interval.Copy the code

Example 2:

Input: ranges = [[1,10],[10,20]], left = 21, right = 21 output: false explanation: 21 is not covered by any range.Copy the code

Tip:


  • 1 < = r a n g e s . l e n g t h < = 50 1 <= ranges.length <= 50

  • 1 < = s t a r t i < = e n d i < = 50 1 <= start_i <= end_i <= 50

  • 1 < = l e f t < = r i g h t < = 50 1 <= left <= right <= 50

simulation

A simple idea is to simulate according to the meaning of the question, check every integer in [left,right][left, right][left,right] [left,right]. If an integer is not covered by the closed range in the rangesRangesranges during the check, Return False and True if all values are checked.

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 code
  • Time complexity: Set the number of integers between [left,right][left, right][left,right] [left,right] to NNN and the length of rangesrangesranges to MMM. Overall complexity is O(n∗m)O(n * m)O(n∗m)
  • Space complexity: O(1)O(1)O(1)

Tree array

There is an interesting extension to this question, which raises the difficulty of the question to [medium] or even [difficult].

[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 rangerangerange [a,b][a, b][a,b].

To do this, we need to use “persistent tree array” or “chairman tree” in conjunction with “inclusive exclusion principle”.

The basic idea is to calculate the counting situation of [a,b][a, b] by subtracting the counting situation of range[0,a−1]range[0, a-1]range[0,a−1].

Back to the problem, since the data range is very small, only 505050, we can use the “tree array” to solve:

  • void add(int x, int u): For numerical values
    x x     Frequency of occurrence
    + u +u     Operation;
  • int query(int x): Queries a satisfaction
    < = x <= x     The number of values of.

CNT =query(x)−query(x−1) CNT =query(x) -query (x-1) CNT =query(x)−query(x−1).

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 code
  • Time complexity: [left,right][left, right][left,right] ∑ I =0range.legth−1ranges[I].length\sum_{I =0}^{range.legth-1}ranges[I].length∑ I =0range.legth−1ranges[I].length Sumsumsum, the constant CCC is fixed at 555555. The tree complexity is O(sumlog⁡C)O(sum\log C)O(sumlogC), and the query complexity is O(nlog⁡C)O(n\log{C})O(nlogC). The overall complexity is O(sumlog⁡C+nlog⁡C)O(sum\log{C} +n \log{C})O(sumlogC+nlogC)
  • Space complexity: O(C)O(C)O(C)

Tree array (de-refactoring)

In the naive “tree array” solution, we cannot directly query the number of overwrites in [L,r][L,r][L,r][L,r] is that “a value may be repeatedly added to the tree array”.

Therefore, a better approach: When I’m adding to the tree array, Then CNT =query(r)− Query (L −1) CNT =query(r) -query (L-1) CNT = Query (r)− Query (L −1) How many numbers are added in the range of [L,r][L,r].

Such a Set de-redo reduces the complexity of our query from O(nlog⁡C)O(n\log{C})O(nlogC) to O(log⁡C)O(\log{C})O(logC).

Since the range of values is small, it is natural to use arrays instead of sets to tag (see P2)

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 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: [left,right][left, right][left,right] ∑ I =0range.legth−1ranges[I].length\sum_{I =0}^{range.legth-1}ranges[I].length∑ I =0range.legth−1ranges[I].length Sumsumsum, the constant CCC is fixed at 555555. The tree complexity is O(sumlog⁡C)O(sum\log C)O(sumlogC), and the query complexity is O(log⁡C)O(\log{C})O(logC). The overall complexity is O(sumlog⁡C+log⁡C)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 marks”)

A more advanced approach is to use “segment trees”, which, like the “tree-array (optimization)” solution, can also be used with persistence to solve “online” problems.

Unlike tree arrays, which mainly solve “single point modification & interval query”, line segment trees can solve most “interval modification (interval modification/single point modification) & interval query” problems.

For this case, since the data range is only 555555, we can use the same idea as the “tree array (optimization)” solution to implement a line segment tree without “lazy tags” (only supports single point modification & interval query).

Code:

class Solution {
    // Indicates that the number of CNT in the interval [l, r] is covered
    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 at the subscript u of tr array and mark at the number 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); }}// From tr array u, query how many values are marked in the range [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);
        returntot == cnt; }}Copy the code
  • Time complexity: [left,right][left, right][left,right] ∑ I =0range.legth−1ranges[I].length\sum_{I =0}^{range.legth-1}ranges[I].length∑ I =0range.legth−1ranges[I].length Sumsumsum, the constant CCC is fixed at 555555. The tree complexity is O(sumlog⁡C)O(sum\log C)O(sumlogC), and the query complexity is O(log⁡C)O(\log{C})O(logC). The overall complexity is O(sumlog⁡C+log⁡C)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 No.1893 of our “Brush through LeetCode” series, which started on 2021/01/01. There are altogether 1916 questions in LeetCode by the start date, some of which have lock questions.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.