0% completed
Problem Statement
Given a 2D array nums
of size N x 2
.
- nums[i] = [start<sub>i</sub>, end<sub>i</sub>], where start<sub>i</sub> is the starting time of the event and end<sub>i</sub> is the ending time of the event.
For each nums[i]
, determine if a requested booking time conflicts with any existing bookings.
Return a boolean array of size N
, representing whether the booking can be done in the given time interval.
Examples
-
Example 1:
- Input: nums = [[10, 20], [15, 25], [20, 30]]
- Expected Output:
[true, false, true]
- Justification: The first event is booked successfully. The second event overlaps with the first one and is rejected. The third event starts when the first event ends, so it's booked successfully.
-
Example 2:
- Input: [[5, 10], [10, 15], [5, 15]]
- Expected Output:
[true, true, false]
- Justification: The first and second events are booked without overlap. The third event overlaps with both the first and second, so it's rejected.
-
Example 3:
- Input: [[8, 13],[13, 17], [17, 20]]
- Expected Output:
[true, true, true]
- Justification: All events are booked without any overlap, as each event starts exactly when the previous one ends.
Constraints:
- 0 <= start < end <= 10<sup>9</sup>
- At most 1000 calls will be made to book.
Solution
To solve this problem, we manage event scheduling in a personal calendar using a TreeSet, a sorted data structure, to store events in order of their start times. The core of the solution involves processing an array of events, where each event is checked for potential overlaps with already scheduled events. This is done by comparing each new event with its closest neighbors in the TreeSet – the nearest events before and after it. If the new event doesn't overlap with these neighbors (i.e., it starts after the preceding event ends and ends before the subsequent event begins), it's added to the TreeSet. Otherwise, it's rejected. This approach efficiently handles multiple event bookings in one operation, ensuring that no two events overlap in the calendar.
-
Initialization:
- Create a data structure (
SortedSet
in C#,TreeSet
in Java,set
in C++, and a list in Python and JavaScript) to store the booked intervals. This data structure will help maintain the intervals in a sorted order based on their start times.
- Create a data structure (
-
Booking Process:
- When a new booking request comes in (represented by a start and end time), we need to determine if it overlaps with any existing bookings.
- Check for two conditions:
- The new booking starts after or exactly when the previous booking ends.
- The new booking ends on or before the next booking starts.
- If both conditions are met, the booking does not overlap with existing bookings, and we can add it to our data structure.
-
Insertion:
- If the booking is successful (i.e., no overlap), add the new interval to the data structure.
-
Returning Results:
- The function should return a boolean value indicating whether the booking was successful (
true
) or not (false
).
- The function should return a boolean value indicating whether the booking was successful (
Example Walkthrough
Let's consider the example where we have the following booking requests: [[10, 20], [15, 25], [20, 30]].
-
Booking
[10, 20]
:- The booking list is empty, so this interval is added without any overlap. The list now contains
[10, 20]
. - Result:
true
- The booking list is empty, so this interval is added without any overlap. The list now contains
-
Booking
[15, 25]
:- We check this against the existing booking
[10, 20]
. The new booking starts before the existing one ends (15 < 20), so this is an overlap. - Result:
false
- We check this against the existing booking
-
Booking
[20, 30]
:- We check this against the existing booking
[10, 20]
. The new booking starts exactly when the existing one ends (20 == 20), so there is no overlap. - The booking
[20, 30]
is added to the list. The list now contains[10, 20]
and[20, 30]
. - Result:
true
- We check this against the existing booking
So, the final results of these booking attempts are [true, false, true]
.
Code
Complexity Analysis
Let:
- ( N ): The number of intervals in the input array
nums
. - ( M ): The number of intervals stored in the
TreeSet
at any point during execution.
Time Complexity
-
Iterating Through Intervals:
- The loop runs ( N ) times, once for each interval in
nums
.
- The loop runs ( N ) times, once for each interval in
-
TreeSet Operations:
-
For each interval, we perform the following operations on the
TreeSet
:lower()
andhigher()
:- Both methods have a time complexity of O(\log M), as the
TreeSet
is implemented using a self-balancing binary search tree.
- Both methods have a time complexity of O(\log M), as the
add()
:- In the worst case, adding an interval to the
TreeSet
also takes O(\log M).
- In the worst case, adding an interval to the
-
Since each interval involves at most three O(\log M) operations, the cost per interval is O(\log M).
-
-
Overall Time Complexity:
- Across ( N ) intervals, the total time complexity is: O(N \cdot \log M)
Space Complexity
-
TreeSet Storage:
- In the worst case, all ( N ) intervals are added to the
TreeSet
. - The
TreeSet
stores ( M ) intervals, where M \leq N. - Space used by the
TreeSet
is proportional to O(M).
- In the worst case, all ( N ) intervals are added to the
-
Auxiliary Storage:
- A
List<Boolean>
of size ( N ) is used to store the results. - The size of this list is O(N).
- A
-
Overall Space Complexity:
- The dominant space is O(N), accounting for both the
TreeSet
and the result list.
- The dominant space is O(N), accounting for both the
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible