My Calendar II
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 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)Returnstrueif the event can be added to the calendar successfully without causing a triple booking. Otherwise, returnfalseand 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
Constraints:
- 0 <= start < end <= 109
- At most
1000calls will be made tobook.
Solve it on LeetCode
Approaches
1. Brute Force with Double Booking Check
Intuition:
The brute force approach involves checking if a new event can be added without causing a double booking. This requires maintaining two lists: one for all booked events and another for overlaps of these events. Every new event is checked against these lists, ensuring it doesn't add a triple booking.
Code:
- Time Complexity: O(n^2), where (n) is the number of calls to the
bookmethod, because each booking may need to check against every other booking for overlap. - Space Complexity: O(n), to store all bookings and potential overlaps.
2. Using ArrayList Overlap and Bookings
Intuition:
An optimization over the previous approach. Instead of blindly checking and updating as in brute force, we focus on preventing any triple bookings by carefully maintaining only necessary overlaps.
Code:
- Time Complexity: O(n^2), similar to the brute force approach.
- Space Complexity: O(n), to maintain lists of bookings and overlaps.
3. TreeMap for Optimized Time Complexity
Intuition:
Using a TreeMap allows us to efficiently track the number of active bookings at any point in time. By incrementing at the start of a booking and decrementing at the end, we can determine double bookings through a sweep-line algorithm.
Code:
- Time Complexity: O(n log n), due to TreeMap operations per booking.
- Space Complexity: O(n), holding start and end times in the map.