leetcode 731. My Calendar II 我的日历

以你之姓@ 2022-06-03 09:00 182阅读 0赞

Implement a MyCalendarTwo class to store your events. A new event can be added if adding the event will not cause a triple booking.

Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval \[start, end), the range of real numbers x such that start <= x < end.

A triple booking happens when three events have some non-empty intersection (ie., there is some time that is common to all 3 events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.

Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)  
Example 1:  
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  
Explanation:  
The first two events can be booked. The third event can be double booked.  
The fourth event (5, 15) can’t be booked, because it would result in a triple booking.  
The fifth event (5, 10) can be booked, as it does not use time 10 which is already double booked.  
The sixth event (25, 55) can be booked, as the time in \[25, 40) will be double booked with the third event;  
the time \[40, 50) will be single booked, and the time \[50, 55) will be double booked with the second event.  
Note:

The number of calls to MyCalendar.book per test case will be at most 1000.  
In calls to MyCalendar.book(start, end), start and end are integers in the range \[0, 10^9\].

本题和上一道题的做法基本一样，first保存的是插入的区间，second保存的是第一次的交区间，只要交区间和插入的区间有交集，表示出第三次的冲突，返回false，否者插入即可

建议和[leetcode 729. My Calendar I][] 和 [leetcode 732. My Calendar III 使用Map记录出入度][leetcode 732. My Calendar III _Map] 一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    
    class MyCalendarTwo
    {
    public:
        set<pair<int, int>> first,second;
        MyCalendarTwo()
        {
    
        }
    
        bool book(int start, int end) 
        {
            for (auto a : second)
            {
                if (a.second <= start || end <= a.first)
                    continue;
                else
                    return false;
            }
    
            for (auto a : first)
            {
                if (a.second <= start || end <= a.first)
                    continue;
                else
                    second.insert({max(a.first,start),min(a.second,end)});
            }
            first.insert({start,end});
            return true;
        }
    };
    
    /**
    * Your MyCalendarTwo object will be instantiated and called as such:
    * MyCalendarTwo obj = new MyCalendarTwo();
    * bool param_1 = obj.book(start,end);
    */

[leetcode 729. My Calendar I]: http://blog.csdn.net/jackzhang_123/article/details/78887019
[leetcode 732. My Calendar III _Map]: http://blog.csdn.net/jackzhang_123/article/details/78887324