My Calendar I
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 (i.e., some moment is common to both 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 MyCalendar class:
MyCalendar()Initializes the calendar object.boolean book(int startTime, int endTime)Returnstrueif the event can be added to the calendar successfully without causing a double booking. Otherwise, returnfalseand do not add the event to the calendar.
Example 1:
Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]
Explanation
Constraints:
- 0 <= start < end <= 109
- At most
1000calls will be made tobook.
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
The brute force approach involves storing every booked interval and iterating through the list whenever a new booking request comes in. This approach checks for conflicts by iterating through each previously booked interval and ensuring no overlap.
Code:
- Time Complexity: O(n), where n is the number of bookings so far. In the worst case, for each new booking, we are checking against all previously stored intervals.
- Space Complexity: O(n) due to storing all booked intervals.
2. Optimized Using TreeMap
Intuition:
To reduce the time complexity for checking overlaps, we can use a TreeMap. The TreeMap data structure maintains the sorted order of starts, which allows faster lookups. We can utilize its floor and ceiling functions to efficiently check for overlaps with neighboring intervals.
Code:
- Time Complexity: O(log n) due to the TreeMap operations (floor, ceiling, and put).
- Space Complexity: O(n) for storing the intervals in the TreeMap.