731. My Calendar II

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 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 <= 10⁹
At most 1000 calls will be made to book.

Solutions

Solution 1: Difference Array

We can use the concept of a difference array to record the booking status at each time point. Then, we traverse all the time points and count the booking status at the current time point. If the number of bookings exceeds $2$, we return $\textit{false}$. Otherwise, we return $\textit{true}$.

The time complexity is $O(n^2)$, and the space complexity is $O(n)$, where $n$ is the number of bookings.

Python3JavaC++GoTypeScriptJavaScript

class MyCalendarTwo:

    def __init__(self):
        self.sd = SortedDict()

    def book(self, startTime: int, endTime: int) -> bool:
        self.sd[startTime] = self.sd.get(startTime, 0) + 1
        self.sd[endTime] = self.sd.get(endTime, 0) - 1
        s = 0
        for v in self.sd.values():
            s += v
            if s > 2:
                self.sd[startTime] -= 1
                self.sd[endTime] += 1
                return False
        return True


# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(startTime,endTime)

class MyCalendarTwo {
    private final Map<Integer, Integer> tm = new TreeMap<>();

    public MyCalendarTwo() {
    }

    public boolean book(int startTime, int endTime) {
        tm.merge(startTime, 1, Integer::sum);
        tm.merge(endTime, -1, Integer::sum);
        int s = 0;
        for (int v : tm.values()) {
            s += v;
            if (s > 2) {
                tm.merge(startTime, -1, Integer::sum);
                tm.merge(endTime, 1, Integer::sum);
                return false;
            }
        }
        return true;
    }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo obj = new MyCalendarTwo();
 * boolean param_1 = obj.book(startTime,endTime);
 */

class MyCalendarTwo {
public:
    MyCalendarTwo() {
    }

    bool book(int startTime, int endTime) {
        ++m[startTime];
        --m[endTime];
        int s = 0;
        for (auto& [_, v] : m) {
            s += v;
            if (s > 2) {
                --m[startTime];
                ++m[endTime];
                return false;
            }
        }
        return true;
    }

private:
    map<int, int> m;
};

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo* obj = new MyCalendarTwo();
 * bool param_1 = obj->book(startTime,endTime);
 */

type MyCalendarTwo struct {
    rbt *redblacktree.Tree[int, int]
}

func Constructor() MyCalendarTwo {
    return MyCalendarTwo{rbt: redblacktree.New[int, int]()}
}

func (this *MyCalendarTwo) Book(startTime int, endTime int) bool {
    merge := func(x, v int) {
        c, _ := this.rbt.Get(x)
        if c+v == 0 {
            this.rbt.Remove(x)
        } else {
            this.rbt.Put(x, c+v)
        }
    }

    merge(startTime, 1)
    merge(endTime, -1)

    s := 0
    for _, v := range this.rbt.Values() {
        s += v
        if s > 2 {
            merge(startTime, -1)
            merge(endTime, 1)
            return false
        }
    }
    return true
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Book(startTime,endTime);
 */

class MyCalendarTwo {
    private tm: Record<number, number> = {};

    constructor() {}

    book(startTime: number, endTime: number): boolean {
        this.tm[startTime] = (this.tm[startTime] ?? 0) + 1;
        this.tm[endTime] = (this.tm[endTime] ?? 0) - 1;
        let s = 0;
        for (const v of Object.values(this.tm)) {
            s += v;
            if (s > 2) {
                if (--this.tm[startTime] === 0) {
                    delete this.tm[startTime];
                }
                if (++this.tm[endTime] === 0) {
                    delete this.tm[endTime];
                }
                return false;
            }
        }
        return true;
    }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * var obj = new MyCalendarTwo()
 * var param_1 = obj.book(startTime,endTime)
 */

var MyCalendarTwo = function () {
    this.tm = {};
};

/**
 * @param {number} startTime
 * @param {number} endTime
 * @return {boolean}
 */
MyCalendarTwo.prototype.book = function (startTime, endTime) {
    this.tm[startTime] = (this.tm[startTime] || 0) + 1;
    this.tm[endTime] = (this.tm[endTime] || 0) - 1;
    let s = 0;

    for (const v of Object.values(this.tm)) {
        s += v;
        if (s > 2) {
            if (--this.tm[startTime] === 0) {
                delete this.tm[startTime];
            }
            if (++this.tm[endTime] === 0) {
                delete this.tm[endTime];
            }
            return false;
        }
    }
    return true;
};

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * var obj = new MyCalendarTwo()
 * var param_1 = obj.book(startTime,endTime)
 */

Solution 2: Segment Tree

A segment tree divides the entire interval into multiple non-contiguous subintervals, with the number of subintervals not exceeding $\log(\textit{width})$. To update the value of an element, only $\log(\textit{width})$ intervals need to be updated, and these intervals are all contained within a larger interval that includes the element. When modifying intervals, a lazy mark is used to ensure efficiency.

Each node of the segment tree represents an interval;
The segment tree has a unique root node representing the entire statistical range, such as $[1, N]$;
Each leaf node of the segment tree represents a unit interval of length 1, $[x, x]$;
For each internal node $[l, r]$, its left child is $[l, \textit{mid}]$ and its right child is $[\textit{mid} + 1, r]$, where $\textit{mid} = \lfloor(l + r) / 2\rfloor$ (i.e., floor division).

For this problem, the segment tree nodes maintain the following information:

The maximum number of bookings within the interval $v$
Lazy mark $\textit{add}$

Since the time range is $10^9$, which is very large, we use dynamic node creation.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the number of bookings.