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.
1using System;
2using System.Collections.Generic;
3
4public class MyCalendar {
5 private List<Tuple<int, int>> calendar;
6
7 public MyCalendar() {
8 calendar = new List<Tuple<int, int>>();
9 }
10
11 public bool Book(int start, int end) {
12 foreach (var interval in calendar) {
13 if (start < interval.Item2 && end > interval.Item1) {
14 return false;
15 }
16 }
17 calendar.Add(Tuple.Create(start, end));
18 return true;
19 }
20
21 public static void Main() {
22 MyCalendar myCalendar = new MyCalendar();
23 Console.WriteLine(myCalendar.Book(10, 20)); // True
24 Console.WriteLine(myCalendar.Book(15, 25)); // False
25 Console.WriteLine(myCalendar.Book(20, 30)); // True
26 }
27}The C# implementation uses a List to store events as Tuples. Overlaps are checked using a loop before a new event is added.
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.