> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/array_problem/729.-my-calendar-i.md).

# 729. My Calendar I

![](/files/-MaS8F-WbyXf1cWU4EyF)

![](/files/-MaS8RyUV4x-z-tNDyt7)

## solution1: use common arraylist compare interval

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

space: O(n)

```java
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;
    }
}
```

```java
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

&#x20;    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`

```java
data[0] < end
```

then use this `data[0]'key to get data[1]'key`&#x20;

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

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

space: O(n)

```java
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...

```java
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
```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)
 */
```
````