[731. My schedule II]

source ： Power button （LeetCode）

describe ：

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⁹].

Code ：

class MyCalendarTwo {
    
public:
    MyCalendarTwo() {
    

    }

    bool book(int start, int end) {
    
        for (auto &[l, r] : overlaps) {
    
            if (l < end && start < r) {
    
                return false;
            }
        }
        for (auto &[l, r] : booked) {
    
            if (l < end && start < r) {
    
                overlaps.emplace_back(max(l, start), min(r, end));
            }
        }
        booked.emplace_back(start, end);
        return true;
    }
private:
    vector<pair<int, int>> booked;
    vector<pair<int, int>> overlaps;
};

Execution time ：76 ms, In all C++ Defeated in submission 97.36% Users of
Memory consumption ：33.1 MB, In all C++ Defeated in submission 96.44% Users of
Complexity analysis
Time complexity ：O(n²), among n Indicates the number of schedules . Because every time I make a reservation , You need to traverse all the scheduled schedules .
Spatial complexity ： O(n), among n Indicates the number of schedules . You need to save all the scheduled trips .

Code ：

class MyCalendarTwo {
    
public:
    MyCalendarTwo() {
    

    }

    bool book(int start, int end) {
    
        int ans = 0;
        int maxBook = 0;
        cnt[start]++;
        cnt[end]--;
        for (auto &[_, freq] : cnt) {
    
            maxBook += freq;
            ans = max(maxBook, ans);
            if (maxBook > 2) {
    
                cnt[start]--;
                cnt[end]++;
                return false;
            }
        }
        return true;
    }
private:
    map<int, int> cnt;
};

Execution time ：192 ms, In all C++ Defeated in submission 79.55% Users of
Memory consumption ：38 MB, In all C++ Defeated in submission 55.34% Users of
Complexity analysis
Time complexity ：O(n²), among n Number of schedules . Each time the maximum reservation is calculated, all schedules need to be traversed .
Spatial complexity ：O(n), among n Number of schedules . Need space to store all schedule counts , The space needed is O(n).

Code ：

class MyCalendarTwo {
    
public:
    MyCalendarTwo() {
    

    }

    void update(int start, int end, int val, int l, int r, int idx) {
    
        if (r < start || end < l) {
    
            return;
        } 
        if (start <= l && r <= end) {
    
            tree[idx].first += val;
            tree[idx].second += val;
        } else {
    
            int mid = (l + r) >> 1;
            update(start, end, val, l, mid, 2 * idx);
            update(start, end, val, mid + 1, r, 2 * idx + 1);
            tree[idx].first = tree[idx].second + max(tree[2 * idx].first, tree[2 * idx + 1].first);
        }
    }

    bool book(int start, int end) {
                
        update(start, end - 1, 1, 0, 1e9, 1);
        if (tree[1].first > 2) {
    
            update(start, end - 1, -1, 0, 1e9, 1);
            return false;
        }
        return true;
    }
private:
    unordered_map<int, pair<int, int>> tree;
};

Execution time ：912 ms, In all C++ Defeated in submission 5.09% Users of
Memory consumption ：293.8 MB, In all C++ Defeated in submission 5.09% Users of
author：LeetCode-Solution