729. My Calendar I

solution1: use common arraylist compare interval

time: O(n), use m times, O(m*n)

space: O(n)

class MyCalendar {
    private List<Integer[]> list;
    
    public MyCalendar() {
        list = new ArrayList<>();
    }
    public boolean book(int start, int end) {
        for (Integer data[] : list) {
            if (data[0] < end && data[1] > start) {
                return false;
            }
        }
        list.add(new Integer[] {start, end});
        return true;
    }
}

data[0] < end && data[1] > start
=>
inEnd > start && end > inStart

s e.  s.  e
---   ----
 inS   inEnd 
  -----
s----------e
     20      30
   15    25
10---20

solution2: use TreeMap

10, 20

15 25

lowerKey(end) => just like this, we find the array start data < end

use end key to find lower key => so get the data[0]'key

data[0] < end

then use this data[0]'key to get data[1]'key

if (low == null || map.get(low) <= start) // data[1] <= start

time: O(logn), use m times, O(mlogn)

space: O(n)

class MyCalendar {
    private TreeMap<Integer, Integer> map;
    public MyCalendar() {
        this.map = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {// store interval in map (start, end)
        Integer low = map.lowerKey(end); // find interval which the start is lower than input end
        if (low == null || this.map.get(low) <= start) { // start >= e, correct case
            this.map.put(start, end);
            return true;
        }
        return false;
    }
}

use native tree, faster but too long...

class MyCalendar {
    class Node {
        private int start;
        private int end;
        private Node left;
        private Node right;
        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    
    private Node root;
    public MyCalendar() {
        root = null;
    }
    
    public boolean book(int start, int end) {
        if(root == null) {
            root = new Node(start, end);
            return true;
        }
        Node node = root;
        while(node != null) {
            if(end <= node.start) {
                if(node.left == null) {
                    node.left = new Node(start, end);
                    return true;
                }
                node = node.left;
            } else if(start >= node.end) {
                if(node.right == null) {
                    node.right = new Node(start, end);
                    return true;
                }
                node = node.right;
            } else {
                return false;
            }
        } 
        return true;
    }
}

latest easy version

```java
class MyCalendar {
ja
    private TreeMap<Integer, Integer> calendar;
    public MyCalendar() {
        calendar = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        Integer ealierThanStart = calendar.floorKey(start);
        Integer laterThanStart = calendar.ceilingKey(start);
        if (laterThanStart != null && end > laterThanStart) {
            return false;
        }
        if (ealierThanStart != null && calendar.get(ealierThanStart) > start) { // if calendar.get(ealierThanStart) < start, then end doest effect, all pass
            return false;
        }
        calendar.put(start, end);
        return true;
    }
}

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

case1: start's ceilingKey

      laterThanStart
  start              end


case2: start's floorKey, then find its end

ealierThanStart        ealierThanStar's end
                 start                        end

                 T: O(logn),  use m times, O(mlogn)
                 S: O(n)
 */
```