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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/array_problem/729.-my-calendar-i.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.