729. My schedule I: "simulation" & "line segment tree (dynamic open point) &" block + bit operation (bucket Division) "

Title Description

This is a LeetCode Upper 729. My schedule I , The difficulty is secondary .

Tag : 「 simulation 」、「 Red and black trees 」、「 Line segment tree （ Dynamic opening point ）」、「 Line segment tree 」、「 Block 」、「 An operation 」、「 Hashtable 」

Achieve one MyCalendar Class to store your schedule . If the schedule to be added does not cause Repeat Booking , You can store this new schedule .

When there is some time overlap between the two schedules （ For example, both schedules are in the same time ）, It will produce Repeat Booking .

The schedule can use a pair of integers start and end Express , The time here is a half open interval , namely , The set of real Numbers   For the range of ,   .

Realization MyCalendar class ：

• MyCalendar() Initialize calendar object .
• boolean book(int start, int end) If the schedule can be successfully added to the calendar without causing duplicate bookings , return true. otherwise , return false  And don't add the schedule to the calendar .

Example ：

 Input ：
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]

 Output ：
[null, true, false, true]

 explain ：
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False , This schedule cannot be added to the calendar , Because of time  15  Has been booked by another schedule .
myCalendar.book(20, 30); // return True , This schedule can be added to the calendar , Because the first schedule is booked at less than each time  20 , And does not include time  20 .

Tips ：

• Each test case , call book The maximum number of methods is Time .

simulation

utilize book The operation can call at most Time , We can use an array to store all the scheduled dates , For every time book operation , Check the current incoming Whether it will conflict with the existing date , Conflict returns False, Otherwise it would be Insert an array and return True.

Code ：

class MyCalendar {
    List<int[]> list = new ArrayList<>();
    public boolean book(int start, int end) {
        end--;
        for (int[] info : list) {
            int l = info[0], r = info[1];
            if (start > r || end < l) continue;
            return false;
        }
        list.add(new int[]{start, end});
        return true;
    }
}

• Time complexity ： Make by book Maximum number of calls , The complexity is
• Spatial complexity ：

Line segment tree （ Dynamic opening point ）

The node information maintained by the segment tree includes ：

• ls/rs: Represent the left and right child nodes of the current node in the segment tree array tr Subscript in ;
• add: Lazy mark ;
• val: Is the number of points contained in the current interval .

For the conventional segment tree implementation , Are called from the beginning build Operation to create an empty tree , The line segment tree is generally represented by 「 Full binary tree 」 Is stored in an array , Therefore need Space , And these spaces are starting build The tree was locked when it was empty .

If a problem is just 「 The range is very large 」 Offline questions for （ Be aware of all enquiries in advance ）, We can still get through 「 discretization 」 To process , Map the value field to a small space , So as to solve MLE problem .

But for this question , because 「 Forced Online 」 Why , We can't do 「 discretization 」, At the same time, the size of the range reaches Level , So if we want to use 「 Line segment tree 」 To solve the , We can only take 「 Dynamic opening point 」 By .

The advantage of dynamic opening point is , There is no need to construct an empty tree in advance , But in the insertion operation add And query operations query According to the needs of access 「 Open point 」 operation . Because we do not guarantee that the query and insert are continuous , So for the parent node for , We can't go through u << 1 and u << 1 | 1 A fixed way to access , Instead, the node The left and right nodes of tr The subscript of the array is stored , Write them down as ls and rs attribute . about and It means that the child node has not been created , When you need to access them , And not yet created , Then create it .

Due to the existence 「 Lazy mark 」, The insertion and query of line segment tree are Of , So when we do a single operation , Up to... Orders of magnitude will be created The point of , So the space complexity is zero , instead of , The estimation of open points should not be based solely on To carry out , Changshu should also be analyzed , To get the exact upper bound of points .

Compared with the original line segment tree, the dynamic open point is realized , The essence is still to use 「 Full binary tree 」 Storage in the form of , It's just creating intervals on demand , If we query or insert according to consecutive segments , In the worst case, it will still account for Space , So blind guess The constant of is about , If you are conservative, you can directly estimate , So we can estimate the number of points as , among and Respectively represent the size of the value range and the number of queries .

Of course, a more practical way of estimating points can 「 Open as many points as possible 」, Using the upper bound of the space given by the topic and the user-defined class we created （ Structure ） Size , Drive as much as possible （ Java Of You can drive to above ）.

Code ：

class MyCalendar {
    class Node {
        // ls  and  rs  The left and right child nodes of the current node are represented in  tr  The subscript 
        // val  Represents the number of current nodes 
        // add  Mark as lazy 
        int ls, rs, add, val;
    }
    int N = (int)1e9, M = 120010, cnt = 1;
    Node[] tr = new Node[M];
    void update(int u, int lc, int rc, int l, int r, int v) {
        if (l <= lc && rc <= r) {
            tr[u].val += (rc - lc + 1) * v;
            tr[u].add += v;
            return ;
        }
        lazyCreate(u);
        pushdown(u, rc - lc + 1);
        int mid = lc + rc >> 1;
        if (l <= mid) update(tr[u].ls, lc, mid, l, r, v);
        if (r > mid) update(tr[u].rs, mid + 1, rc, l, r, v);
        pushup(u);
    }
    int query(int u, int lc, int rc, int l, int r) {
        if (l <= lc && rc <= r) return tr[u].val;
        lazyCreate(u);
        pushdown(u, rc - lc + 1);
        int mid = lc + rc >> 1, ans = 0;
        if (l <= mid) ans = query(tr[u].ls, lc, mid, l, r);
        if (r > mid) ans += query(tr[u].rs, mid + 1, rc, l, r);
        return ans;
    }
    void lazyCreate(int u) {
        if (tr[u] == null) tr[u] = new Node();
        if (tr[u].ls == 0) {
            tr[u].ls = ++cnt;
            tr[tr[u].ls] = new Node();
        }
        if (tr[u].rs == 0) {
            tr[u].rs = ++cnt;
            tr[tr[u].rs] = new Node();
        }
    }
    void pushdown(int u, int len) {
        tr[tr[u].ls].add += tr[u].add; tr[tr[u].rs].add += tr[u].add;
        tr[tr[u].ls].val += (len - len / 2) * tr[u].add; tr[tr[u].rs].val += len / 2 * tr[u].add;
        tr[u].add = 0;
    }
    void pushup(int u) {
        tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val;
    }
    public boolean book(int start, int end) {
        if (query(1, 1, N + 1, start + 1, end) > 0) return false;
        update(1, 1, N + 1, start + 1, end, 1);
        return true;
    }
}

• Time complexity ： Make Is the value range size , This topic is fixed as , The query of segment tree and the increase of complexity are
• Spatial complexity ： Let the number of inquiries be , The complexity is

Block + An operation （ Points barrels ）

Another regretful algorithm is 「 Block 」, The naive blocking method is to use a Boolean array region Represents whether a block is occupied , Use a hash table to record whether a specific location is occupied , But unfortunately, it was blocked by the strange evaluation mechanism .

image.png

TLE Code ：

class MyCalendar {
    static Boolean T = Boolean.TRUE, F = Boolean.FALSE;
    static int n = (int)1e9, len = (int) Math.sqrt(n) + 30;
    static boolean[] region = new boolean[len];
    static Map<Integer, Boolean> map = new HashMap<>();
    int getIdx(int x) {
        return x / len;
    }
    void add(int l, int r) {
        if (getIdx(l) == getIdx(r)) {
            for (int k = l; k <= r; k++) map.put(k, T);
        } else {
            int j = l, i = r;
            while (getIdx(j) == getIdx(l)) map.put(j++, T);
            while (getIdx(i) == getIdx(r)) map.put(i--, T);
            for (int k = getIdx(j); k <= getIdx(i); k++) region[k] = true;
        }
    }
    boolean query(int l, int r) {
        if (getIdx(l) == getIdx(r)) {
            boolean cur = region[getIdx(l)];
            for (int k = l; k <= r; k++) {
                if (map.getOrDefault(k, F) || cur) return false;
            }
            return true;
        } else {
            int j = l, i = r;
            while (getIdx(j) == getIdx(l)) {
                if (map.getOrDefault(j, F) || region[getIdx(j)]) return false;
                j++;
            }
            while (getIdx(i) == getIdx(r)) {
                if (map.getOrDefault(i, F) || region[getIdx(i)]) return false;
                i--;
            }
            for (int k = getIdx(j); k <= getIdx(i); k++) {
                if (region[k]) return false;
            }
            return true;
        }
    }
    public MyCalendar() {
        Arrays.fill(region, false);
        map.clear();
    }
    public boolean book(int start, int end) {
        if (query(start, end - 1)) {
            add(start, end - 1);
            return true;
        }
        return false;
    }
}

But we know that the complexity of the blocking algorithm is not bad , The hash table may be the key to the stuck constant , So we can use int Array to act as a hash table , Because you only need to record 「 Is it occupied 」, So we can use int Each of them acts as a lattice , Through this kind of 「 Points barrels + An operation 」, Effective reduction constant .

AC Code （2022-07-05 Passable ）：

class MyCalendar {
    static int n = (int)1e9, len = (int) Math.sqrt(n) + 50, cnt = 32;
    static boolean[] region = new boolean[len];
    static int[] map = new int[n / cnt];
    int getIdx(int x) {
        return x / len;
    }
    boolean get(int x) {
        return ((map[x / cnt] >> (x % cnt)) & 1) == 1;
    }
    void set(int x) {
        map[x / cnt] |= (1 << (x % cnt));
    }
    void add(int l, int r) {
        if (getIdx(l) == getIdx(r)) {
            for (int k = l; k <= r; k++) set(k);
        } else {
            int j = l, i = r;
            while (getIdx(j) == getIdx(l)) set(j++);
            while (getIdx(i) == getIdx(r)) set(i--);
            for (int k = getIdx(j); k <= getIdx(i); k++) region[k] = true;
        }
    }
    boolean query(int l, int r) {
        if (getIdx(l) == getIdx(r)) {
            boolean cur = region[getIdx(l)];
            for (int k = l; k <= r; k++) {
                if (get(k) || cur) return false;
            }
            return true;
        } else {
            int j = l, i = r;
            while (getIdx(j) == getIdx(l)) {
                if (get(j) || region[getIdx(j)]) return false;
                j++;
            }
            while (getIdx(i) == getIdx(r)) {
                if (get(i) || region[getIdx(i)]) return false;
                i--;
            }
            for (int k = getIdx(j); k <= getIdx(i); k++) {
                if (region[k]) return false;
            }
            return true;
        }
    }
    public MyCalendar() {
        Arrays.fill(region, false);
        Arrays.fill(map, 0);
    }
    public boolean book(int start, int end) {
        if (query(start, end - 1)) {
            add(start, end - 1);
            return true;
        }
        return false;
    }
}

• Time complexity ：
• Spatial complexity ： , among Is the value range size , The number of cells that can be stored for a single number

Last

This is us. 「 Brush through LeetCode」 The first of the series No.729 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases