Li Kou 729. My schedule I

Title source ：https://leetcode.cn/problems/my-calendar-i/

General meaning ：
Set up a MyCalendar class , It includes the following functions ：

• 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 .

Ideas

Use the segment tree to save the schedule , Every time you add a schedule , Mark the interval corresponding to the schedule in the segment tree . Before each addition , First check whether there is any added time period in the current schedule interval , If yes, do not add this schedule .

Because the number of nodes used in the segment tree is about the range of nodes 4 times , The range of ontology nodes is [0, 10⁹], Too much scope , It is not suitable for directly applying for space . Therefore, the dynamic opening method is adopted , Every time you put in a schedule , Dynamically create segment tree nodes related to the schedule interval . And use lazy tags to mark whether the intervals covered by the current node have been scheduled .

The specific operations of adding a schedule are as follows ：

1. First, judge whether the corresponding interval of the schedule has been added , When querying, you can judge whether nodes have been created in the query interval by lazy tags ： If there are lazy tags or nodes in the query interval are created , Then the interval must have been added
2. If the whole interval has not been inserted , Then the dynamic opening point is inserted into the schedule

Code ：

public class MyCalendar_SegmentTree {
    
    Set<Integer> tree;  //  Indicates that there is a predetermined interval within the node range 
    Set<Integer> lazy;  //  It means that all nodes are scheduled 
    int BORDER; //  Maximum range of nodes 

    public MyCalendar_SegmentTree() {
    
        tree = new HashSet<>();
        lazy = new HashSet<>();
        BORDER = (int) 1e9;
    }

    public boolean book(int start, int end) {
    
        //  First, query whether the current schedule interval has been inserted 
        if (query(start, end - 1, 0, BORDER, 1)) {
    
            return false;
        }
        //  Insert current schedule 
        update(start, end - 1, 0, BORDER, 1);
        return true;
    }

    /** *  Inquire about  [start, end]  Whether there are segment tree nodes in the interval , If yes, it means that there is a predetermined part in the interval  * * @param start * @param end * @param l  The left boundary of the current line segment tree node  * @param r  The right boundary of the current line segment tree node  * @param idx  Current segment tree node number  * @return */
    public boolean query(int start, int end, int l, int r, int idx) {
    
        //  The current segment tree node does not contain the query range 
        if (r < start || end < l) {
    
            return false;
        }
        //  If the range of nodes is predetermined , Go straight back to  true
        if (lazy.contains(idx)) {
    
            return true;
        }
        //  The range of current segment tree nodes is within the query range 
        if (start <= l && r <= end) {
    
            //  So as long as the segment tree node exists , It means that the node range of the line segment tree has been predetermined 
            return tree.contains(idx);
        }
        int mid = (l + r) >> 1;
        //  The query range is only in the left node of the segment tree 
        if (end <= mid) {
    
            return query(start, end, l, mid, idx * 2);
        } else if (mid < start) {
     //  The query range is only in the right node of the segment tree 
            return query(start, end, mid + 1, r, idx * 2 + 1);
        } else {
        //  The query range spans two sub nodes of the segment tree 
            return query(start, end, l, mid, idx * 2) || query(start, end, mid + 1, r, idx * 2 + 1);
        }
    }

    /** *  Scheduled interval  [start, end] * * @param start * @param end * @param l  The left boundary of the current line segment tree node  * @param r  The right boundary of the current line segment tree node  * @param idx  Current segment tree node number  */
    public void update(int start, int end, int l, int r, int idx) {
    
        if (r < start || end < l) {
    
            return;
        }
        //  The range of the current segment tree node is within the update range 
        if (start <= l && r <= end) {
    
            tree.add(idx);
            lazy.add(idx);
        } else {
    
            int mid = (l + r) >> 1;
            if (mid >= end) {
       //  The update range is only at the left node of the segment tree 
                update(start, end, l, mid, idx * 2);
            } else if (mid < start) {
       //  The update range is only at the right node of the segment tree 
                update(start, end, mid + 1, r, idx * 2 + 1);
            } else {
        //  The update range spans the left and right nodes of the segment tree 
                update(start, end, l, mid, idx * 2);
                update(start, end, mid + 1, r, idx * 2 + 1);
            }
            //  There is a predetermined interval in the node range of the current line segment tree 
            tree.add(idx);
        }
    }

    public static void main(String[] args) {
    
        MyCalendar_SegmentTree tree = new MyCalendar_SegmentTree();
        System.out.println(tree.book(10, 20));
        System.out.println(tree.book(15, 25));
        System.out.println(tree.book(20, 30));
    }
}