731. My Calendar II

Description

The problem requires designing a class MyCalendarTwo that supports the booking of events, but with the restriction that triple bookings (an event that overlaps with two or more existing events) are not allowed. The class should provide a method book(start, end) that returns true if the event can be added to the calendar without causing any triple bookings, and false otherwise. We are allowed to have double bookings, but no triple bookings.

Intuition

To handle this problem, the key observation is that for a triple booking to occur, an event must overlap with two or more previously booked events. So, for every new booking, we need to:

1. Check if the new event overlaps with any already overlapping events (this would imply a triple booking).
2. If no triple booking occurs, update the list of overlapping events for any double-booked events.
3. Finally, add the new event to the main calendar.

Approach

1. Maintain two lists: - calendar: This stores all the booked events. - overlaps: This stores events that have been double-booked (i.e., overlap with at least one other event).
2. When a new booking is requested via book(start, end): - First, iterate through the overlaps list to see if the new event would cause a triple booking. If it overlaps with any event in the overlaps list, return false. - If no triple booking occurs, iterate through the calendar list to check for overlaps with the new event. If an overlap is found, calculate the overlapping interval and add it to the overlaps list (to track double bookings). - Finally, add the new event to the calendar.
3. Return true if the event can be successfully booked without causing a triple booking.

Complexity

• Time Complexity: The time complexity for each booking operation is O(n), where n is the number of events in the calendar list. This is because we need to check all previously booked events for overlaps and, in the worst case, iterate through all of them.
• Space Complexity: The space complexity is also O(n) because we are maintaining two lists (calendar and overlaps), both of which could grow linearly with the number of events.

Code

C++

class MyCalendarTwo {
public:
    vector> calendar;
    vector> overlaps;

    MyCalendarTwo() {}

    bool book(int start, int end) {
        for (const auto& date : overlaps) {
            if (start < date.second && end > date.first) {
                return false;
            }
        }

        for (const auto& date : calendar) {
            if (start < date.second && end > date.first) {
                overlaps.push_back({max(date.first, start), min(date.second, end)});
            }
        }

        calendar.push_back({start, end});
        return true;
    }
};

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

Python

class MyCalendarTwo:

    def __init__(self):
        self.calendar = []
        self.overlaps = []

    def book(self, start: int, end: int) -> bool:
        for date in self.overlaps:
            if start < date[1] and end > date[0]:
                return False

        for date in self.calendar:
            if start < date[1] and end > date[0]:
                self.overlaps.append((max(date[0], start), min(date[1], end)))

        self.calendar.append((start, end))
        return True

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

Java

class MyCalendarTwo {
    private List calendar;
    private List overlaps;

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

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

        for (int[] date : calendar) {
            if (start < date[1] && end > date[0]) {
                overlaps.add(new int[] {Math.max(date[0], start), Math.min(date[1], end)});
            }
        }

        calendar.add(new int[] {start, end});
        return true;
    }
}

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

JavaScript

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

MyCalendarTwo.prototype.book = function(start, end) {
    for(let date of this.overlaps){
        if(start < date[1] && end > date[0]) 
            return false;
    }
    for(let date of this.calendar){
        if(start < date[1] && end > date[0]){
            this.overlaps.push([Math.max(date[0], start), Math.min(date[1], end)]);
        }
    }
    this.calendar.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)
 */