731. My schedule II (segment tree or scoring array)

Achieve one MyCalendar Class to store your schedule . If the time to be added does not result in triple booking , You can store this new schedule .

MyCalendar There is one book(int start, int end) Method . It means in start To end Add a schedule in time , Be careful , The time here is a half open interval , namely [start, end), The set of real Numbers  x For the range of ,  start <= x < end.

When the three schedules have some time overlap （ For example, all three schedules are at the same time ）, There will be triple bookings .

Every time you call MyCalendar.book When the method is used , If the schedule can be successfully added to the calendar without triple booking , return true. otherwise , return false And don't add the schedule to the calendar .

Please follow the steps below to call MyCalendar class : MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

Example ：

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true
explain ： 
The first two schedules can be added to the calendar . The third schedule will lead to double booking , But it can be added to the calendar .
Fourth schedule activity （5,15） Can't add to calendar , Because it leads to triple booking .
The fifth schedule （5,10） Can be added to the calendar , Because it doesn't use the time that has been double reserved 10.
Sixth schedule （25,55） Can be added to the calendar , Because of time [25,40] Double booking with the Third Schedule ;
Time [40,50] Will book separately , Time [50,55） Double booking with the second schedule .
 

Tips ：

Each test case , call  MyCalendar.book  The function is no more than  1000 Time .
Call function  MyCalendar.book(start, end) when , start and  end The value range of is  [0, 10^9].

Score checking array ：

class MyCalendarTwo {
private:
    map<int, int> differential_array_book; //  Difference array 
public:
    MyCalendarTwo() {
    }
    
    bool book(int start, int end) {
        //  Suppose the schedule is successfully inserted 
        //  Using the characteristics of differential array , The following operation is equivalent to setting the date [start,end) Number of schedules +1
        differential_array_book[start]++;
        differential_array_book[end]--;

        int book_num = 0;
        for(auto it = differential_array_book.begin(); it != differential_array_book.end();it++) {
            book_num += it->second; //  Use the difference array feature to calculate the number of schedules for a certain date 
            if(book_num >= 3) {
                //  If there is a triple reservation , Rollback schedule insert 
                differential_array_book[start]--;
                differential_array_book[end]++;
                //  This operation is just to save time , It has no effect on correctness 
                //  The difference array is 0 It's the default , You can delete 
                if(differential_array_book[start] == 0)
                    differential_array_book.erase(start);
                return false;
            }
        }
        return true;
    }
};

Line segment tree ：

class MyCalendarTwo {
    /**
     *  Node of segment tree 
     */
    static class Node {
        // Left range 
        private int leftX;
        // Right range 
        private int rightX;
        // Maximum 
        private int max;
        // Lazy mark  0 Indicates that no operation is required 
        private int lazy;
        // Left subtree and right subtree 
        Node leftChild, rightChild;

        public Node(int leftX, int rightX) {
            this.leftX = leftX;
            this.rightX = rightX;
        }
    }

    private Node root;

    /**
     *  Interval update 
     *
     * @param root   The root of the tree 
     * @param left   Left boundary 
     * @param right  Boundary 
     * @param value  Update value , Deleting is equivalent to setting 0
     */
    public void update(Node root, int left, int right, int value) {
        // Out of range   Go straight back to 
        if (root.leftX > right || root.rightX < left) {
            return;
        }
        // The modified interval contains the current node 
        if (root.leftX >= left && root.rightX <= right) {
            root.max += value;
            root.lazy += value;
        } else {
            // Dynamic opening point 
            lazyCreate(root);
            // Next lazy
            pushDown(root);
            // Update left subtree 
            update(root.leftChild, left, right, value);
            // Update right subtree 
            update(root.rightChild, left, right, value);
            // Upload results 
            pushUp(root);
        }
    }

    public int query(Node root, int left, int right) {
        if (left <= root.leftX && root.rightX <= right) {
            return root.max;
        }
        lazyCreate(root);
        pushDown(root);
        int mid = root.leftX + (root.rightX - root.leftX) / 2;
        if (right <= mid) {
            return query(root.leftChild, left, right);
        } else if (left > mid) {
            return query(root.rightChild, left, right);
        } else {
            return Math.max(query(root.leftChild, left, mid), query(root.rightChild, mid + 1, right));
        }
    }

    /**
     *  Create left and right subtrees 
     *
     * @param root
     */
    public void lazyCreate(Node root) {
        if (root.leftChild == null) {
            root.leftChild = new Node(root.leftX, root.leftX + (root.rightX - root.leftX) / 2);
        }
        if (root.rightChild == null) {
            root.rightChild = new Node(root.leftX + (root.rightX - root.leftX) / 2 + 1, root.rightX);
        }
    }

    /**
     *  Next lazy
     *
     * @param root
     */
    public void pushDown(Node root) {
        if (root.lazy > 0) {
            int value = root.lazy;
            root.leftChild.lazy += value;
            root.rightChild.lazy += value;
            root.leftChild.max += value;
            root.rightChild.max += value;
            root.lazy = 0;
        }
    }

    /**
     *  Upload results 
     *
     * @param root
     */
    public void pushUp(Node root) {
        root.max = Math.max(root.leftChild.max, root.rightChild.max);
    }

    public MyCalendarTwo() {
        root = new Node(0, (int) 1e9);
    }

    public boolean book(int start, int end) {
        int query = query(root, start, end - 1);
        if (query >= 2) {
            return false;
        }
        update(root, start, end - 1, 1);
        return true;
    }
}