Problem 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 double booking. A double booking happens when two events have some non-empty intersection. The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime).
Implement the MyCalendar class:
- MyCalendar() 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 double booking. Otherwise, return false and do not add the event to the calendar.
Key Insights
- Events are represented as half-open intervals.
- A double booking occurs if the start time of a new event is less than the end time of an existing event and the end time of the new event is greater than the start time of an existing event.
- Efficiently managing bookings can be achieved using a sorted list to maintain the intervals.
Space and Time Complexity
Time Complexity: O(n) for each booking in the worst case, where n is the number of events already booked (if we check against all existing bookings). However, using binary search can improve the search for overlaps to O(log n).
Space Complexity: O(n) for storing the booked events.
Solution
To solve this problem, we can use a list to keep track of all the booked events. When a new booking request is made, we can iterate through the list to check if the new booking overlaps with any existing bookings. If there is no overlap, we add the new booking to the list and return true; otherwise, we return false. To optimize the search for overlaps, we can maintain the list in sorted order and use binary search.