# My Calendar II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/my-calendar-ii)
Canonical: https://scaleengineer.com/dsa/problems/my-calendar-ii
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Segment Tree, Ordered Set
---
## 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 **triple booking**.

A **triple booking** happens when three events have some non-empty intersection (i.e., some moment is common to all the three 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 `MyCalendarTwo` class:

* `MyCalendarTwo()` 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 **triple booking**. Otherwise, return `false` and do not add the event to the calendar.

**Example 1:**

**Input**
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
**Output**
[null, true, true, true, false, true, true]

**Explanation**
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // return True, The event can be booked. 
myCalendarTwo.book(50, 60); // return True, The event can be booked. 
myCalendarTwo.book(10, 40); // return True, The event can be double booked. 
myCalendarTwo.book(5, 15);  // return False, The event cannot be booked, because it would result in a triple booking.
myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked.
myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

**Constraints:**

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

# Approaches
## Brute Force with Two Lists
This approach maintains two lists: one for all booked events (`bookings`) and another for all double-booked time intervals (`overlaps`). When a new event is to be booked, we first check if it intersects with any of the existing double-booked intervals. If it does, it would create a triple booking, so we reject the event. If it doesn't, we accept the event, add it to our `bookings` list, and then update the `overlaps` list by checking the new event against all previously booked events.
**Time:** O(N^3) for N calls. The k-th call takes O(k^2) time because the number of overlaps can be O(k^2). The total time is the sum of k^2 for k from 1 to N. · **Space:** O(N^2), where N is the number of bookings. The `bookings` list stores N events, but the `overlaps` list can store up to O(N^2) intervals.
**Pros:** Conceptually straightforward and relatively easy to implement.
**Cons:** Highly inefficient `O(N^3)` time complexity for `N` calls.; High space complexity of `O(N^2)`.
### Explanation
We initialize two lists, `bookings` and `overlaps`. For each `book(start, end)` call:

1.  **Check for Triple Booking**: Iterate through the `overlaps` list. For each interval `[o_start, o_end)` in `overlaps`, check if it intersects with the new event `[start, end)`. An intersection occurs if `start < o_end` and `end > o_start`. If an intersection is found, it means a triple booking would occur. We return `false` immediately.

2.  **Update Overlaps**: If no triple booking is detected, we proceed to add the event. But first, we must identify any new double-booked intervals created by this new event. We iterate through the `bookings` list. For each existing event `[b_start, b_end)`, we calculate its intersection with `[start, end)`. The intersection is `[max(start, b_start), min(end, b_end))`. If this intersection is non-empty (i.e., the start is less than the end), we add this new double-booked interval to the `overlaps` list.

3.  **Add Event**: After updating the `overlaps`, we add the new event `[start, end)` to the `bookings` list.

4.  Return `true` to indicate a successful booking.

```java
class MyCalendarTwo {
    private List<int[]> bookings;
    private List<int[]> overlaps;

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

    public boolean book(int start, int end) {
        for (int[] o : overlaps) {
            if (start < o[1] && end > o[0]) {
                return false; // Triple booking
            }
        }

        for (int[] b : bookings) {
            int overlapStart = Math.max(start, b[0]);
            int overlapEnd = Math.min(end, b[1]);
            if (overlapStart < overlapEnd) {
                overlaps.add(new int[]{overlapStart, overlapEnd});
            }
        }

        bookings.add(new int[]{start, end});
        return true;
    }
}
```
### Algorithm
- Initialize two lists, `bookings` to store all events and `overlaps` to store all double-booked intervals.
- When `book(start, end)` is called:
  1. Iterate through each interval `o` in the `overlaps` list. If the new event `[start, end)` intersects with `o`, it would create a triple booking. Return `false`.
  2. If no triple booking is found, iterate through the `bookings` list. For each existing event `b`, calculate the intersection with `[start, end)`. If the intersection is non-empty, add it to the `overlaps` list.
  3. Add the new event `[start, end)` to the `bookings` list.
  4. Return `true`.

## Boundary Counting (Sweep-line Algorithm)
This approach treats the start and end points of events as significant moments in time. We use a sorted map (like a `TreeMap` in Java) to store the change in the number of active events at each boundary point. A start point `s` increments the count (`+1`), and an end point `e` decrements it (`-1`). To check if a new event `[start, end)` can be booked, we tentatively add its boundaries to the map. Then, we sweep across the timeline by iterating through the map's keys, calculating the cumulative number of active events at each point. If this number ever reaches 3, a triple booking would occur.
**Time:** O(N^2) for N calls. The k-th call involves adding two entries to the map (O(log k)) and then iterating through O(k) entries. So, each call is O(k). The total time is the sum of k from 1 to N. · **Space:** O(N), where N is the number of bookings. The `TreeMap` will store at most 2N boundary points.
**Pros:** A significant improvement in time and space complexity over the brute-force approach.; Elegant solution based on the sweep-line paradigm.
**Cons:** The `O(N^2)` time complexity might be too slow for a very large number of calls, although it passes the given constraints.
### Explanation
We use a `TreeMap` named `delta` to store boundary points as keys and the change in active event count as values.

For each `book(start, end)` call:
1.  **Tentative Update**: We tentatively add the new event's boundaries to the `delta` map. We increment the count at `start` by 1 and decrement the count at `end` by 1.
    `delta.put(start, delta.getOrDefault(start, 0) + 1);`
    `delta.put(end, delta.getOrDefault(end, 0) - 1);`
2.  **Sweep and Check**: We initialize an `active_events` counter to 0. We iterate through the values of the `delta` map in chronological order (which `TreeMap` provides). At each time point, we add the corresponding delta value to `active_events`. After each update, we check if `active_events` is 3 or more.
3.  **Handle Triple Booking**: If `active_events` reaches 3, it signifies a triple booking. We must revert the changes made in step 1 by decrementing the count at `start` and incrementing it at `end`. Then, we return `false`.
4.  **Confirm Booking**: If the sweep completes without the active event count ever reaching 3, the booking is valid. The tentative changes are now permanent, and we return `true`.

```java
class MyCalendarTwo {
    private TreeMap<Integer, Integer> delta;

    public MyCalendarTwo() {
        delta = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        delta.put(start, delta.getOrDefault(start, 0) + 1);
        delta.put(end, delta.getOrDefault(end, 0) - 1);

        int activeEvents = 0;
        for (int d : delta.values()) {
            activeEvents += d;
            if (activeEvents >= 3) {
                // Revert changes
                delta.put(start, delta.get(start) - 1);
                if (delta.get(start) == 0) {
                    delta.remove(start);
                }
                delta.put(end, delta.get(end) + 1);
                if (delta.get(end) == 0) {
                    delta.remove(end);
                }
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Use a `TreeMap` to store boundary points and the change in active events (+1 for start, -1 for end).
- When `book(start, end)` is called:
  1. Tentatively update the map: `map[start]++` and `map[end]--`.
  2. Initialize an `active_events` counter to 0.
  3. Iterate through the map's values in chronological order. Sum up the changes to `active_events`.
  4. If `active_events` ever reaches 3, a triple booking is detected. Revert the changes to the map and return `false`.
  5. If the loop completes, the booking is valid. Return `true`.

## Segment Tree with Lazy Propagation
This is the most efficient approach, utilizing a segment tree data structure to handle the range updates and queries. The problem's time coordinates can be very large (`10^9`), so we use a dynamic segment tree (where nodes are created on-demand) to avoid allocating a massive array. Each node in the tree represents a time interval and stores the maximum number of overlapping events within that interval. Lazy propagation is used to efficiently apply updates to large ranges.
**Time:** O(N * log C), where N is the number of bookings and C is the maximum coordinate value (10^9). Each call to `book` performs a query and an update, both taking O(log C) time. · **Space:** O(N * log C), where N is the number of bookings and C is the maximum coordinate value. Each update on the dynamic segment tree can create O(log C) new nodes.
**Pros:** Optimal time complexity, making it very fast for a large number of calls.; Handles a very large coordinate range efficiently.
**Cons:** Significantly more complex to implement correctly compared to other approaches.; The constant factors associated with the complexity might be larger, making it slower for very small N.
### Explanation
We build a dynamic segment tree over the range `[0, 10^9]`. Each node will store `max_val`, the maximum number of concurrent bookings in its corresponding interval, and `lazy`, a value for lazy propagation.

The `book(start, end)` logic is as follows:
1.  **Query**: Before making any changes, we query the segment tree for the interval `[start, end)`. This query will find the maximum number of events that are already booked at any single point within this new interval.
2.  **Check for Triple Booking**: If the result of the query is 2 or more, it means some point in `[start, end)` is already double-booked. Adding the new event would create a triple booking. In this case, we return `false`.
3.  **Update**: If the query result is less than 2, the booking is permissible. We then perform an update operation on the segment tree for the interval `[start, end)`, incrementing the booking count for this range by 1. This is done efficiently using lazy propagation.
4.  Return `true`.

The `query(range)` operation finds the maximum value in the given range, and the `update(range, value)` operation adds `value` to all elements in the given range. Both operations take `O(log C)` time, where `C` is the maximum coordinate value.

```java
class MyCalendarTwo {
    private static class Node {
        int maxVal;
        int lazy;
        Node left, right;
    }

    private Node root;
    private final int MAX_COORD = 1_000_000_000;

    public MyCalendarTwo() {
        root = new Node();
    }

    private void push(Node node) {
        if (node.lazy > 0) {
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            node.left.lazy += node.lazy;
            node.left.maxVal += node.lazy;
            node.right.lazy += node.lazy;
            node.right.maxVal += node.lazy;
            node.lazy = 0;
        }
    }

    private void update(Node node, int start, int end, int l, int r, int val) {
        if (l > r || l > end || r < start) {
            return;
        }
        if (l >= start && r <= end) {
            node.lazy += val;
            node.maxVal += val;
            return;
        }
        
        push(node);
        
        int mid = l + (r - l) / 2;
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        
        update(node.left, start, end, l, mid, val);
        update(node.right, start, end, mid + 1, r, val);
        
        node.maxVal = Math.max(node.left.maxVal, node.right.maxVal);
    }

    private int query(Node node, int start, int end, int l, int r) {
        if (l > r || node == null || l > end || r < start) {
            return 0;
        }
        if (l >= start && r <= end) {
            return node.maxVal;
        }

        push(node);

        int mid = l + (r - l) / 2;
        int leftQuery = query(node.left, start, end, l, mid);
        int rightQuery = query(node.right, start, end, mid + 1, r);
        
        return Math.max(leftQuery, rightQuery);
    }

    public boolean book(int start, int end) {
        int maxBookings = query(root, start, end - 1, 0, MAX_COORD);
        if (maxBookings >= 2) {
            return false;
        }
        update(root, start, end - 1, 0, MAX_COORD, 1);
        return true;
    }
}
```
### Algorithm
- Implement a dynamic Segment Tree with lazy propagation over the coordinate range `[0, 10^9]`.
- Each node in the tree stores `max_val` (maximum bookings in its range) and a `lazy` tag for updates.
- When `book(start, end)` is called:
  1. Query the segment tree for the range `[start, end - 1]` to find the maximum number of existing overlaps.
  2. If the result is 2 or more, return `false` as it would cause a triple booking.
  3. Otherwise, update the segment tree for the range `[start, end - 1]` by incrementing the booking count by 1.
  4. Return `true`.

# Solutions
### Java

```java
class MyCalendarTwo { private Map < Integer , Integer > tm = new TreeMap <>(); public MyCalendarTwo () { } public boolean book ( int start , int end ) { tm . put ( start , tm . getOrDefault ( start , 0 ) + 1 ); tm . put ( end , tm . getOrDefault ( end , 0 ) - 1 ); int s = 0 ; for ( int v : tm . values ()) { s += v ; if ( s > 2 ) { tm . put ( start , tm . get ( start ) - 1 ); tm . put ( end , tm . get ( end ) + 1 ); return false ; } } return true ; } } /** * Your MyCalendarTwo object will be instantiated and called as such: * MyCalendarTwo obj = new MyCalendarTwo(); * boolean param_1 = obj.book(start,end); */
```

### JavaScript

```javascript
var MyCalendarTwo = function () { this . events = []; this . overlaps = []; }; /** * @param {number} start * @param {number} end * @return {boolean} */ MyCalendarTwo . prototype . book = function ( start , end ) { for ( let [ s , e ] of this . overlaps ) { if ( Math . max ( start , s ) < Math . min ( end , e )) { return false ; } } for ( let [ s , e ] of this . events ) { if ( Math . max ( start , s ) < Math . min ( end , e )) { this . overlaps . push ([ Math . max ( start , s ), Math . min ( end , e )]); } } this . events . push ([ start , end ]); return true ; }; /** * Your MyCalendarTwo object will be instantiated and called as such: * var obj = new MyCalendarTwo() * var param_1 = obj.book(start,end) */
```

### CPP

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

### Python

```python
from sortedcontainers import SortedDict class MyCalendarTwo : def __init__ ( self ): self . sd = SortedDict () # cannot be dict like self.sd={} def book ( self , start : int , end : int ) -> bool : self . sd [ start ] = self . sd . get ( start , 0 ) + 1 self . sd [ end ] = self . sd . get ( end , 0 ) - 1 s = 0 for v in self . sd . values (): s += v if s > 2 : self . sd [ start ] -= 1 self . sd [ end ] += 1 return False return True # Your MyCalendarTwo object will be instantiated and called as such: # obj = MyCalendarTwo() # param_1 = obj.book(start,end) ############ class MyCalendarTwo ( object ): def __init__ ( self ): # 每个被book了的区间 self . booked = list () # 每个重叠了的区间 self . overlaped = list () def book ( self , start , end ): """ :type start: int :type end: int :rtype: bool """ for os , oe in self . overlaped : if max ( os , start ) < min ( oe , end ): return False for bs , be in self . booked : ss = max ( bs , start ) ee = min ( be , end ) if ss < ee : self . overlaped . append (( ss , ee )) self . booked . append (( start , end )) return True # Your MyCalendarTwo object will be instantiated and called as such: # obj = MyCalendarTwo() # param_1 = obj.book(start,end)
```