algoadvance

Problem Statement

731. My Calendar II

Implement a MyCalendarTwo class to store your events. A new event can be added if adding the event will not cause a triple booking.

Your class will have one method, book(int start, int end), where start and end represent the start and end times of the event. The method should return true if the event can be added without causing a triple booking, and false otherwise.

An event is a triple booking if there are three events that overlap at some point.

Example

MyCalendarTwo myCalendar = new MyCalendarTwo();
myCalendar.book(10, 20); // returns true
myCalendar.book(50, 60); // returns true
myCalendar.book(10, 40); // returns true
myCalendar.book(5, 15);  // returns false
myCalendar.book(5, 10);  // returns true
myCalendar.book(25, 55); // returns true

Clarifying Questions

1. Does an event include the end time?
   • No, the event is considered to start at start and end just before end.
2. What is the range of time values we can expect for start and end?
   • Typically, time values are non-negative integers, with start < end.
3. Can start and end values be negative or zero?
   • In usual scenarios, time values are positive integers.
4. What are the constraints on the number of operations?
   • Typically, constraints are around a reasonable limit to ensure performance (e.g., 1 ≤ start, end ≤ 10^9).

Strategy

We can keep track of two calendars:

1. Single Bookings: Track events that have at least one booking.
2. Double Bookings: Track events that have exactly two overlapping events.

When trying to book a new event, we first check if it will cause a triple booking by overlapping with any of the double bookings. If it does, we return false. If not, we then update our single and double booking tracks accordingly and return true.

Code

class MyCalendarTwo:

    def __init__(self):
        self.bookings = []
        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.bookings:
            if start < b_end and end > b_start:
                self.overlaps.append((max(start, b_start), min(end, b_end)))
        
        self.bookings.append((start, end))
        return True

# Example usage:
# myCalendar = MyCalendarTwo()
# print(myCalendar.book(10, 20)) # returns True
# print(myCalendar.book(50, 60)) # returns True
# print(myCalendar.book(10, 40)) # returns True
# print(myCalendar.book(5, 15))  # returns False
# print(myCalendar.book(5, 10))  # returns True
# print(myCalendar.book(25, 55)) # returns True

Time Complexity

Let ( n ) be the number of events booked so far.

• Initialization: The constructor (__init__) runs in O(1) time.
• Booking an Event: In the worst case, for every booking, we need to check against all the previous bookings and overlaps. Therefore, the complexity for booking an event is O(n), where n is the number of bookings made before the current one.

Overall, the implementation ensures that we iteratively check and record overlaps, maintaining efficiency within acceptable limits for typical input sizes expected in such problems.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?