Sponsored
Sponsored
This approach uses a simple list to store existing bookings. For each new booking, we check against all previously booked intervals to ensure there is no overlap. If an overlap is found, the booking is denied; otherwise, it's added to the list. Although straightforward, this approach can be inefficient for many bookings, as each booking incurs a linear scan through the list of existing bookings.
Time Complexity: O(N) for each booking, where N is the number of existing bookings.
Space Complexity: O(N) for storing the bookings.
1class MyCalendar {
2 constructor() {
3 this.booked = [];
4 }
5
6 book(start, end) {
7 for (const [s, e] of this.booked) {
8 if (start < e && end > s) {
9 return false;
10 }
11 }
12 this.booked.push([start, end]);
13 return true;
14 }
15}
16
17const myCalendar = new MyCalendar();
18console.log(myCalendar.book(10, 20)); // True
19console.log(myCalendar.book(15, 25)); // False
20console.log(myCalendar.book(20, 30)); // TrueJavaScript utilizes an array to manage bookings, stored as subarrays. The 'book' function iterates through these arrays, checking overlaps before adding a new booking.
This approach leverages a data structure like a TreeMap (Java) or SortedDict (Python) to efficiently manage and query intervals. These structures allow us to quickly find the nearest existing intervals to check for overlaps, enabling faster insert operations compared to a simple list. By maintaining the intervals in a sorted order, we can reduce the number of overlaps checks necessary for each new booking.
Time Complexity: O(log N) for each booking due to TreeMap operations.
Space Complexity: O(N).
1import java.util.TreeMap;
In this Java solution, a TreeMap is used to maintain ordered bookings. 'floorKey' and 'ceilingKey' efficiently find adjacent bookings to check for overlaps with the new booking's start and end times.