# My Calendar I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/my-calendar-i)
Canonical: https://scaleengineer.com/dsa/problems/my-calendar-i
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Skip List](https://scaleengineer.com/algorithms/skip-list)
**Data structures:** Array, Segment Tree, Ordered Set
**Companies:** [Flexport](https://scaleengineer.com/companies/flexport)
---
## Problem
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 `startTime` and `endTime` that represents a booking on the half-open interval `[startTime, endTime)`, the range of real numbers `x` such that `startTime <= x < endTime`.

Implement the `MyCalendar` class:

* `MyCalendar()` Initializes the calendar object.
* `boolean book(int startTime, int endTime)` 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`.

# Approaches
## Brute Force using a List
This approach uses a simple list to store all the booked events. For each new booking request, it iterates through the entire list of existing events to check for any overlaps. While straightforward, its performance degrades as the number of events increases.
**Time:** O(N) per `book` call. For `k` existing bookings, we iterate through all `k` of them. Since there can be up to `N` calls, the `k`-th call can take O(k) time. The total time for `N` calls is O(N^2). · **Space:** O(N), where N is the number of successful bookings. We need to store each booked event.
**Pros:** Simple to understand and implement.; Requires minimal code and standard data structures.
**Cons:** Inefficient for a large number of bookings as the time for each `book` operation grows linearly with the number of events already in the calendar.
### Explanation
We maintain a simple `ArrayList` to store the event intervals. Each event is represented as an array of two integers, `[startTime, endTime)`.

When the `book(start, end)` method is called, we perform a linear scan through our list of already booked events. For each existing event `[s, e)`, we check if it has a non-empty intersection with the new event `[start, end)`. Two half-open intervals `[s1, e1)` and `[s2, e2)` overlap if and only if `s1 < e2` and `s2 < e1`.

If an overlap is detected with any event in the list, we know it's a double booking. We immediately return `false` and do not add the new event to the calendar. If we successfully iterate through the entire list without finding any conflicts, it signifies that the time slot is free. We then add the new event `[start, end)` to our list and return `true`.

```java
import java.util.ArrayList;
import java.util.List;

class MyCalendar {
    private List<int[]> bookings;

    public MyCalendar() {
        bookings = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        for (int[] b : bookings) {
            // Check for overlap: max(start_A, start_B) < min(end_A, end_B)
            if (Math.max(b[0], start) < Math.min(b[1], end)) {
                return false;
            }
        }
        bookings.add(new int[]{start, end});
        return true;
    }
}
```
### Algorithm
- Initialize a list, `bookings`, to store the event intervals `[start, end)`.
- When `book(start, end)` is called, iterate through every event `b` already in the `bookings` list.
- For each event `b = [s, e)`, check if the new event `[start, end)` overlaps with it. The condition for an overlap is `start < e` and `s < end`. A more concise way to check this is `Math.max(start, s) < Math.min(end, e)`.
- If an overlap is found with any existing event, the new event cannot be booked. Return `false` immediately.
- If the loop completes without finding any overlaps, the booking is valid. Add the new event `[start, end)` to the `bookings` list and return `true`.

## Balanced Binary Search Tree (TreeMap)
This optimized approach leverages a balanced binary search tree (specifically, a `TreeMap` in Java) to maintain the events in sorted order. By keeping the events sorted by their start times, we can check for potential overlaps in logarithmic time instead of linear time, leading to a significant performance improvement.
**Time:** O(log N) per `book` call. `TreeMap` operations like `lowerKey` and `put` take O(log k) time, where `k` is the current number of events. The total time for `N` calls is O(N log N). · **Space:** O(N), where N is the number of successful bookings. The `TreeMap` stores one entry per event.
**Pros:** Highly efficient with logarithmic time complexity per booking.; Scales very well as the number of events in the calendar grows.
**Cons:** More complex to reason about the logic compared to the brute-force approach.; Has a slightly higher constant factor overhead due to the tree data structure.
### Explanation
Instead of a list, we use a `TreeMap` where keys are the event start times and values are the end times. This structure automatically maintains the events sorted by their start times, which is key to the optimization.

When a new event `[start, end)` is requested, we don't need to check every single past event. Since the existing events are sorted and non-overlapping, a new event can only conflict with its immediate neighbors in the time line. More specifically, any potential conflict must involve an existing event `[s, e)` that starts before the new event ends (`s < end`) and ends after the new event starts (`e > start`).

A very elegant way to check this is to find the single most likely candidate for an overlap: the event that starts latest but still before the new event's `end` time. We can find its start time `s_p` using `TreeMap.lowerKey(end)`. If this event `[s_p, e_p)` exists, we only need to check if it extends into our new event's time, i.e., if `e_p > start`. If this condition is met, we have a double booking. Otherwise, no event can possibly overlap.

If no conflict is found, we add the new event to the `TreeMap`. The search (`lowerKey`) and insertion (`put`) operations on a `TreeMap` take logarithmic time.

```java
import java.util.TreeMap;

class MyCalendar {
    private TreeMap<Integer, Integer> calendar;

    public MyCalendar() {
        calendar = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        // Find the latest booking that starts before the new event ends.
        Integer prevStart = calendar.lowerKey(end);

        // If such a booking exists, check if it overlaps with the new event.
        // Overlap occurs if the previous event's end time is after the new event's start time.
        if (prevStart != null && calendar.get(prevStart) > start) {
            return false;
        }

        // If no overlap, add the new event and return true.
        calendar.put(start, end);
        return true;
    }
}
```
### Algorithm
- Use a `TreeMap` to store events, mapping start times (keys) to end times (values). The `TreeMap` keeps events sorted by their start times.
- When `book(start, end)` is called, we need to check for overlaps with potential neighbors.
- An overlap can only occur with an event `[s, e)` where `s < end` and `e > start`.
- We can efficiently check this by finding the event `[s_p, e_p)` with the largest start time `s_p` that is still less than our new event's `end` time. This is done using `calendar.lowerKey(end)`.
- If such an event `[s_p, e_p)` exists, we check if it overlaps with `[start, end)`. The overlap condition simplifies to checking if `e_p > start`.
- If `e_p > start`, there is an overlap, so we return `false`.
- If no such conflicting event is found, the booking is valid. We insert the new event `(start, end)` into the `TreeMap` and return `true`.

# Solutions
### Java

```java
import java.util.Map ; import java.util.TreeMap ; class MyCalendar { private final TreeMap < Integer , Integer > tm = new TreeMap <>(); public MyCalendar () { } public boolean book ( int start , int end ) { Map . Entry < Integer , Integer > ent = tm . floorEntry ( start ); if ( ent != null && ent . getValue () > start ) { return false ; } ent = tm . ceilingEntry ( start ); if ( ent != null && ent . getKey () < end ) { return false ; } tm . 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); */
```

### JavaScript

```javascript
var MyCalendar = function () { this . calendar = []; }; /** * @param {number} start * @param {number} end * @return {boolean} */ MyCalendar . prototype . book = function ( start , end ) { for ( const item of this . calendar ) { if ( end <= item [ 0 ] || item [ 1 ] <= start ) { continue ; } return false ; } this . calendar . push ([ start , end ]); return true ; }; /** * Your MyCalendar object will be instantiated and called as such: * var obj = new MyCalendar() * var param_1 = obj.book(start,end) */
```

### CPP

```cpp
class MyCalendar { public: map < int , int > m ; MyCalendar () { } bool book ( int start , int end ) { ++ m [ start ]; -- m [ end ]; int s = 0 ; for ( auto & [ k , v ] : m ) { s += v ; if ( s > 1 ) { -- m [ start ]; ++ m [ end ]; return false ; } } return true ; } }; /** * Your MyCalendar object will be instantiated and called as such: * MyCalendar* obj = new MyCalendar(); * bool param_1 = obj->book(start,end); */
```

### Python

```python
''' >>> sd SortedDict({'a': 111, 'b': 222, 'c': 333}) >>> sd.keys() SortedKeysView(SortedDict({'a': 111, 'b': 222, 'c': 333})) >>> sd.values() SortedValuesView(SortedDict({'a': 111, 'b': 222, 'c': 333})) >>> sd.items() SortedItemsView(SortedDict({'a': 111, 'b': 222, 'c': 333})) >>> >>> >>> sd.keys()[1] 'b' >>> sd.values()[1] 222 >>> sd.append({'aaa':111}) Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'SortedDict' object has no attribute 'append' >>> >>> sd.add({'aaa':111}) Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'SortedDict' object has no attribute 'add' ''' from sortedcontainers import SortedDict class MyCalendar : def __init__ ( self ): self . sd = SortedDict () def book ( self , start : int , end : int ) -> bool : # bisect_left will not work, due to duplicates # eg: [[],[10,20],[15,25],[20,30]] idx = self . sd . bisect_right ( start ) # self.sd.keys()[idx] ==> end time # self.sd.values()[idx] ==> it's start time if idx < len ( self . sd ) and end > self . sd . values ()[ idx ]: return False self . sd [ end ] = start return True # Your MyCalendar object will be instantiated and called as such: # obj = MyCalendar() # param_1 = obj.book(start,end) ############ class Node ( object ): # double linked list, full scan def __init__ ( self , s , e ): self . s = s self . e = e self . left = None self . right = None class MyCalendar ( object ): def __init__ ( self ): self . root = None def book_helper ( self , s , e , node ): if node . e <= s : if node . right : return self . book_helper ( s , e , node . right ) else : node . right = Node ( s , e ) return True elif node . s >= e : if node . left : return self . book_helper ( s , e , node . left ) else : node . left = Node ( s , e ) return True else : return False def book ( self , start , end ): """ :type start: int :type end: int :rtype: bool """ if not self . root : self . root = Node ( start , end ) return True else : return self . book_helper ( start , end , self . root ) # Your MyCalendar object will be instantiated and called as such: # obj = MyCalendar() # param_1 = obj.book(start,end)
```