729. My Calendar I

吸等 (celingKey 是有等於的

Though1

class MyCalendar {

    TreeMap<Integer, Integer> map;
    public MyCalendar() {
        map = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        Integer later = map.ceilingKey(start);
        Integer ealier = map.floorKey(start);
        if (later != null && end > later) {
            return false;
        }
        if (ealier != null && map.get(ealier) > start) {
            return false;
        }
        map.put(start, end);
        return true;
    }
}

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

use start as key to compare in TreeMap!

4 cases:

     10       x    -> later = null, ealier = 10, get(ealier) > s
        s e

     10      x          -> later = null, , ealier = 10, get(ealier) > s
          s      e

     10      x       -> later = 10, e > later
  s      e  

       10      x
  s                   e    -> later = 10        , e > later    


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

ps: only start can be compare by key

5 10
case1 
  
  10       20
      
      
s      e  

       later == null
       so ealier is 10, so get(ealier) = 20 > s
  10       20
       s        e 

case2

    later = null
    so earlier is 10,   get(ealier) = 20 > s       
   10       20
       s e
 






 */

thought 2

only care when can put (simpler)

這題比較特別, treeMap 放的是 (start, end), key is start value

use lowerKey()

T: book: O(nlogn), n is booked times, each time we insert new data with logn,treeMap is red-black tree
S: O(n)

class MyCalendar {

    TreeMap<Integer, Integer> map;
    public MyCalendar() {
        map = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        Integer low = map.lowerKey(end);
        // 比 end 小的值, 沒有跟 start 重疊, 就可以 booking
        // 這樣也可以保證, 沒有跟 end 重疊
        if (low == null || map.get(low) <= start) { 
            map.put(start, end);
            return true;
        }
        return false;
    }
}

/**
  low
   |----|
|-----|     =>. map.get(low) > s
s.    e


       low
   |----|
      |-----|     =>. map.get(low) > s
      s.    e
      
     low
 |----|
      |-----|     =>. map.get(low) == s, it's ok
      s.    e  
      
    low
|----|
       |-----|     =>. map.get(low) < s, it's ok
       s.    e 

               
                |----|
       |-----|     =>. map.get(low) == null, it's ok
       s.    e 
       
             |----|
       |-----|     =>. map.get(low) == null, it's ok (that's why use lowerKey)
       s.    e 

 
     20    30
 10  20
   15.  25 
   
   T: book: O(logn), treeMap is red-black tree
   S: O(n)
 */729. My Calendar I

Though 3 - can used for Calender 2 (n^2)

use sweep line, but need to iterate map, so time complexity is worse

class MyCalendar {

    private TreeMap<Integer, Integer> map;
    public MyCalendar() {
        map = new TreeMap<Integer, Integer>();
    }
    
    // O(nlogn) (if book n times)
    // public boolean book(int start, int end) {
    //     Integer lowerKey = map.lowerKey(end);
    //     if (lowerKey == null || map.get(lowerKey) <= start) {
    //         map.put(start, end);
    //         return true;
    //     }
    //     return false;
    // }
    
    // n(logn + n) (if book n times, n is the map key size as well in worst case)
    public boolean book(int start, int end) {
        map.put(start, map.getOrDefault(start, 0)+1);
        map.put(end, map.getOrDefault(end, 0)-1);
        int count = 0;
        for (int value : map.values()) {
            count += value;
            if (count > 1) {
                map.put(start, map.getOrDefault(start, 0)-1);
                map.put(end, map.getOrDefault(end, 0)+1);

                if (map.get(start) == 0) {
                    map.remove(start);
                }
                return false;
            }
        }
        return true;
    }
}

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

use floorKey(), ceilingKey()

For Java, we will have a TreeMap where the keys are the start of each interval, and the values are the ends of those intervals. 
When inserting the interval [start, end), 
we check if there is a conflict on each side with neighboring intervals: 
we would like calendar.get(prev)) <= start <= end <= next for the booking to be valid (or for prev or next to be null respectively.)

其實只有用到 start, so TreeMap<start, end>

case of able to book 
 satrt               start
 prev <=         <=  next    
         |-----|
        start. end

class MyCalendar {

    TreeMap<Integer, Integer> map;
    public MyCalendar() {
        map = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        Integer prev = map.floorKey(start);
        Integer next = map.ceilingKey(start);
        if ((prev == null || map.get(prev) <= start) &&
           (next == null || end <= next)) { // this is key compare
            map.put(start, end);
            return true;
        }
        return false;
    }
}

/**
For Java, we will have a TreeMap where the keys are the start of each interval, and the values are the ends of those intervals. 
When inserting the interval [start, end), 
we check if there is a conflict on each side with neighboring intervals: 
we would like calendar.get(prev)) <= start <= end <= next for the booking to be valid (or for prev or next to be null respectively.)

其實只有用到 start, so TreeMap<start, end>

case of able to book 
 satrt               start
 prev <=         <=  next    
         |-----|
        start. end

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

sweep-line

also suit for 731, just change the max > ?

T: O(nlogn + n^2) = O(n^2), n times to call book()

S: O(n)

class MyCalendar {

    TreeMap<Integer, Integer> map;
    public MyCalendar() {
        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()) { // O(n)
            count += value;
            max = Math.max(max, count);
            if (max > 1) {
                
                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;
    }
}