Code Implementation

class MyCalendarTwo:
    def __init__(self):
        self.booked = []
        self.overlaps = []

    def book(self, start: int, end: int) -> bool:
        for o_start, o_end in self.overlaps:
            if start < o_end and end > o_start:
                return False
        for b_start, b_end in self.booked:
            if start < b_end and end > b_start:
                self.overlaps.append((max(start, b_start), min(end, b_end)))
        self.booked.append((start, end))
        return True
      

class MyCalendarTwo {
public:
    vector<pair<int, int>> booked;
    vector<pair<int, int>> overlaps;
    MyCalendarTwo() {}
    
    bool book(int start, int end) {
        for (auto &o : overlaps) {
            if (start < o.second && end > o.first)
                return false;
        }
        for (auto &b : booked) {
            if (start < b.second && end > b.first) {
                overlaps.push_back({max(start, b.first), min(end, b.second)});
            }
        }
        booked.push_back({start, end});
        return true;
    }
};
      

class MyCalendarTwo {
    List<int[]> booked;
    List<int[]> overlaps;

    public MyCalendarTwo() {
        booked = 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;
            }
        }
        for (int[] b : booked) {
            if (start < b[1] && end > b[0]) {
                overlaps.add(new int[]{Math.max(start, b[0]), Math.min(end, b[1])});
            }
        }
        booked.add(new int[]{start, end});
        return true;
    }
}
      

var MyCalendarTwo = function() {
    this.booked = [];
    this.overlaps = [];
};

MyCalendarTwo.prototype.book = function(start, end) {
    for (let [oStart, oEnd] of this.overlaps) {
        if (start < oEnd && end > oStart) {
            return false;
        }
    }
    for (let [bStart, bEnd] of this.booked) {
        if (start < bEnd && end > bStart) {
            this.overlaps.push([Math.max(start, bStart), Math.min(end, bEnd)]);
        }
    }
    this.booked.push([start, end]);
    return true;
};
      

Problem Description

The My Calendar II problem asks you to design a calendar booking system that supports double bookings, but not triple bookings. Specifically, you need to implement a class with a book(start, end) method:

• Each call to book(start, end) attempts to add a new event from start (inclusive) to end (exclusive).
• The method should return true if the event can be added without causing any time to be triple-booked (i.e., no time is covered by three or more events).
• If the event would cause a triple booking, book should return false and not add the event.

The key constraint is: no time slot can be booked more than twice. You must ensure that, after each booking, at most two events overlap at any given moment.

Thought Process

The first idea that comes to mind is to keep a list of all booked events and, for each new booking, check how many events overlap with the new one. If at any time the overlap count reaches three, we reject the booking.

However, this brute-force approach can be inefficient, especially when there are many bookings. We need to optimize by only tracking the critical overlaps, rather than examining every possible interval.

By thinking carefully, we realize that a triple booking happens only when a new event overlaps with two or more existing events at the same time. So, if we keep track of all the intervals where two events already overlap, we can simply check if the new event overlaps with any of these "double-booked" intervals. If it does, a triple booking would occur.

Solution Approach

We use two lists:

• booked: Stores all the single-booked intervals (all events ever booked).
• overlaps: Stores all the intervals where two events overlap (i.e., double-booked intervals).

1. For each new book(start, end) call, first check if it overlaps with any interval in overlaps. If so, return false (triple booking would occur).
2. If not, for each interval in booked, check if it overlaps with the new interval. If so, the overlapping part is a new "double-booked" interval, so add it to overlaps.
3. Finally, add the new interval to booked and return true.

This approach ensures that we only ever allow at most two overlapping events at any time, efficiently detecting triple bookings.

Example Walkthrough

Suppose we call:

• book(10, 20) → No overlaps, so add to booked. Returns true.
• book(50, 60) → No overlaps, so add to booked. Returns true.
• book(10, 40) → Overlaps with (10, 20), so add (10, 20) to overlaps. Add (10, 40) to booked. Returns true.
• book(5, 15) → Overlaps with (10, 20) and (10, 40). The overlap with (10, 20) is (10, 15), and with (10, 40) is (10, 15). So, add (10, 15) to overlaps. But before that, check if (5, 15) overlaps with any interval in overlaps. It does: (10, 15). So, this would cause a triple booking. Returns false.

This demonstrates how the algorithm prevents triple bookings while allowing double bookings.

Time and Space Complexity

Brute-force approach:

• For each booking, we would need to check all existing bookings for overlaps, and possibly count the number of overlaps at every point in time. This could be O(N^2) per booking for N bookings.

• For each booking, we check overlaps with all double-booked intervals (O(M), where M is the number of double-booked intervals), and then with all single bookings (O(N)). So, per booking, the complexity is O(N + M).
• Both booked and overlaps lists can grow up to O(N^2) in the worst case (if every booking partially overlaps with every previous one).
• Overall, for K bookings, the worst-case time is O(K^2), but in practice, it's much faster for sparse bookings.

Space Complexity: O(N^2) for storing all overlaps in the worst case.

Summary

The solution to My Calendar II uses two lists to efficiently track bookings and double-booked intervals. By checking overlaps with double-booked intervals before adding a new booking, we prevent triple bookings. This approach is both simple and effective, balancing clarity and efficiency, and avoids the need for complex data structures or brute-force checking of every possible overlap.