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.
1import java.util.ArrayList;
2import java.util.List;
3
4class MyCalendar {
5 List<int[]> calendar;
6
7 public MyCalendar() {
8 calendar = new ArrayList<>();
9 }
10
11 public boolean book(int start, int end) {
12 for (int[] event : calendar) {
13 if (start < event[1] && end > event[0]) {
14 return false;
15 }
16 }
17 calendar.add(new int[]{start, end});
18 return true;
19 }
20
21 public static void main(String[] args) {
22 MyCalendar myCalendar = new MyCalendar();
23 System.out.println(myCalendar.book(10, 20)); // True
24 System.out.println(myCalendar.book(15, 25)); // False
25 System.out.println(myCalendar.book(20, 30)); // True
26 }
27}In the Java solution, an ArrayList holds the events. The 'book' method iterates through the list, checking for overlapping intervals before adding a new event.
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).
1#include <map>
2#include <iostream>
3
4class MyCalendar {
public:
MyCalendar() {}
bool book(int start, int end) {
auto next = calendar.lower_bound(start);
if (next != calendar.end() && next->first < end) {
return false;
}
if (next != calendar.begin()) {
auto prev = std::prev(next);
if (prev->second > start) {
return false;
}
}
calendar[start] = end;
return true;
}
private:
std::map<int, int> calendar;
};
int main() {
MyCalendar myCalendar;
std::cout << myCalendar.book(10, 20) << std::endl; // True
std::cout << myCalendar.book(15, 25) << std::endl; // False
std::cout << myCalendar.book(20, 30) << std::endl; // True
return 0;
}C++ utilizes a map to keep bookings sorted by keys. Methods 'lower_bound' fetch the closest next booking and checks with the previous booking to manage overlaps efficiently.