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.
1#include <stdbool.h>
2#include <stdio.h>
3
4#define MAX_EVENTS 1000
5
6int booked[MAX_EVENTS][2];
7int count = 0;
8
9bool book(int start, int end) {
10 for (int i = 0; i < count; i++) {
11 if (start < booked[i][1] && end > booked[i][0]) {
12 return false;
13 }
14 }
15 booked[count][0] = start;
16 booked[count][1] = end;
17 count++;
18 return true;
19}
20
21int main() {
22 printf("%d\n", book(10, 20)); // True
23 printf("%d\n", book(15, 25)); // False
24 printf("%d\n", book(20, 30)); // True
25 return 0;
26}This C program maintains a two-dimensional array 'booked' which stores the start and end of each booking. The 'book' function iterates through existing bookings and checks for overlap. If no overlap is found, it adds the 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).
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.