# 0729. My Calendar I

<https://leetcode.com/problems/my-calendar-i>

## Description

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a **double booking**.

A **double booking** happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers `start` and `end` that represents a booking on the half-open interval `[start, end)`, the range of real numbers `x` such that `start <= x < end`.

Implement the `MyCalendar` class:

* `MyCalendar()` Initializes the calendar object.
* `boolean book(int start, int end)` Returns `true` if the event can be added to the calendar successfully without causing a **double booking**. Otherwise, return `false` and do not add the event to the calendar.

**Example 1:**

```
**Input**
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
**Output**
[null, true, false, true]
**Explanation**
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.
```

**Constraints:**

* `0 <= start < end <= 109`
* At most `1000` calls will be made to `book`.

## ac1: TreeMap

```java
class MyCalendar {
    TreeMap<Integer, Integer> tmap;
    public MyCalendar() {
        tmap = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        Integer f = tmap.floorKey(start);
        Integer c = tmap.ceilingKey(start);
        if (f != null && tmap.get(f) > start || c != null && end > c) {
            return false;
        }
        tmap.put(start, end);
        return true;
    }
}
// O(logN) query and insert
```

Can be more concise:

```java
TreeMap<Integer, Integer> map;
public MyCalendar() {
    map = new TreeMap<>();
}

public boolean book(int start, int end) {
    Integer low = map.lowerKey(end);
    
    if(low == null || map.get(low) <= start) {
        map.put(start, end);
        return true;
    }
    return false;
}
```

## ac2: Doublely LinkedList + Binary Search

* Use Doublely LinkedList to store intervals;
* Binary search find insertion index of start, check if it's valid. Just like above TreeMap approach. Benefit: O(logN) lookup, O(1) insert. The code is lengthy though.


---

# 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://jaywin.gitbook.io/leetcode/solutions/0729-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.