Leetcode -1893- Checks whether all integers in the region are overwritten

[Blog link]

The way to study 🐔

The nuggets home page

[Topic description]

Give you a two-dimensional array of integers ranges and two integers left and right. Each ranges[I] = [starti, endi] represents a closed interval from Star Ti 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. Example 2: input: ranges = [[1,10],[10,20]], left = 21, right = 21 output: false description: 21 is not covered by any of the ranges. Tip: 1 <= ranges. Length <= 50 1 <= starti <= endi <= 50 1 <= left <= right <= 50 Related Topics array hash table prefix and 👍 32 👎 0Copy the code

[Topic link]

Leetcode title link

[making address]

Code link

[思路介绍]

Idea 1: Violence

  • Iterates over each element between left and right
  • Every time I find one, I go down until I’ve traversed all the elements in the interval
public boolean isCovered(int[][] ranges, int left, int right) { for (int i = left; i <= right; i++) { boolean isValid = false; for (int[] range: ranges ) { if (i>=range[0] && i<=range[1]){ isValid = true; break; } } if (! isValid){ return false; } } return true; }Copy the code

Time complexity O(n*C) n is range length, C is right-left interval length

Idea 2: Differential arrays

  • It was fun to learn a new algorithm
  • The official problem is a little stupid, or write too tianshu can not understand
  • [Lao Gan Ma is omnipotent] this big guy’s explanation is much clearer
  • The algorithm for splitting an array as I understand it goes like this
  • Define a difference array so that for each interval, the element at the beginning of the interval corresponds to +1
  • The next element at the end of the interval corresponds to -1
  • And then finally the difference array prefixes and >0 are the elements in the range
  • The outside is outside the current interval
  • Because they’re limiting the size, the diff interval is pretty easy to do
public boolean isCovered(int[][] ranges, int left, int right) {
            int[] diff = new int[52];
            for (int[] range : ranges
            ) {
                diff[range[0]]++;
                diff[range[1] + 1]--;
            }
            int[] sum = new int[52];
            for (int i = 1; i < 52; i++) {
               sum[i] = sum[i-1] + diff[i];
            }
            for (int i = left; i <= right; i++) {
                if (sum[i] <= 0) {
                    return false;
                }
            }
            return true;
        }
Copy the code

The time complexity is O(n+c), where n is the range length and c is the right-left interval length

Idea 3: Tree array

  • This is a new data structure
  • Thanks to the big Guy (@answerer) for the guidance
  • Core lowbit function
  • I will write a separate article on the specific data structure
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
O ( ∑ 1 n C + l o g C ) O(\sum_1^{n}C + log_{C})

Segment tree and tree array after optimization together!