731. My Calendar II

Thought 1: use sweep line again ->

book() -> n*(logn + n) = O(nlogn + n^2) = O(n^2), n times to call book()

S: O(n)

class MyCalendarTwo {

    TreeMap<Integer, Integer> map;
    public MyCalendarTwo() {
        map = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        map.put(start, map.getOrDefault(start, 0)+1);
        map.put(end, map.getOrDefault(end, 0)-1);
        
        int max = 0;
        int count = 0;
        for (int value : map.values()) {
            count += value;
            max = Math.max(max, count);
            if (max > 2) {
                
                map.put(start, map.get(start)-1);
                map.put(end, map.get(end)+1);
                if (map.get(start) == 0) {
                    map.remove(start);
                }
                if (map.get(end) == 0) {
                    map.remove(end);
                }
                
                return false;
            }
        }

        return true;
    }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo obj = new MyCalendarTwo();
 * boolean param_1 = obj.book(start,end);
 */

Thought 2 use overlapping list to check the triplet booking - T: O(n)

overlapping list means record the overlapped part of two booking, then if there is the third one has the overlapped part, it's tripplet booking!

T: O(n)
S: O(n)

class MyCalendarTwo {

    private List<int[]> bookings;
    private List<int[]> overlappedBookings;
    public MyCalendarTwo() {
        bookings = new ArrayList<>();
        overlappedBookings = new ArrayList<>();
    }
    
    public boolean book(int start, int end) {
        for (int[] booking : overlappedBookings) {
            if (!(start >= booking[1] || end <= booking[0])) { // if there is a third overlapping..
                return false; 
            }
        }
        for (int[] booking : bookings) {
            if (!(start >= booking[1] || end <= booking[0])) { // if these 2 have overlapping
                overlappedBookings.add(new int[] {Math.max(start, booking[0]), Math.min(end, booking[1])});
            }
        }
        bookings.add(new int[] {start, end});
        return true;
    }
}

/**
T: O(n)
S: O(n)


not overlapping is these 2 or
|   |      |.  | 
    s      e
|. |         |. |


make overlapped interval list

use overlapped interval -> means there are 2 time interval is overlapped! 
so if the incoming interval is in this range! it's a tripple booking! return false



 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo obj = new MyCalendarTwo();
 * boolean param_1 = obj.book(start,end);
 */