title

problem link

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.

solution

求是否三个区间重合，

时间线作法

每次扫描线走一下，使用treemap实现可以避免每次排序，时间复杂度每次是O(n)

class MyCalendarTwo {
    TreeMap<Integer, Integer> event2count;
    public MyCalendarTwo() {
        this.event2count =  = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
      // 先假设这个event能被放进去
      event2count.put(start, event2count.getOrDefault(start, 0) + 1);
      event2count.put(end, event2count.getOrDefault(end, 0) - 1);
      
      int count = 0;
      // 扫描线
      for(Map.Entry<Integer, Integer> entry : event2count.entrySet()){
        count += entry.getValue();
        
        // 放进去发现不符合要求, 拿出来return false
        if(count >= 3){
          event2count.put(start, event2count.get(start) - 1);
          event2count.put(end, event2count.get(end) + 1);
          return false;
        }
      }
      
      return true;
    }
}

下面是存了不重合的，存了重合的，然后遍历判断， o(n2)

class MyCalendarTwo {
public:
	vector<pair<int,int>> calendar, overlap;
	MyCalendarTwo() {

	}

	bool book(int start, int end) {
		for (auto it : overlap) {
			if (start<it.second&&end>it.first) {
				return false;
			}
		}
		for (auto it : calendar) {
			if (start<it.second&&end>it.first) {
				overlap.push_back(make_pair(max(start, it.first), min(end, it.second)));
			}
		}
		calendar.push_back(make_pair(start, end));
		return true;
	}
};