grid47 Exploring patterns and algorithms
Aug 25, 2024
6 min read
Solution to LeetCode 731: My Calendar II Problem
You are implementing a calendar system where you can add events. Each event is represented by a start time and an end time, defined as a half-open interval [startTime, endTime). You need to ensure that no more than two events overlap at any given time, or else return false. Your task is to implement a class, MyCalendarTwo, that will book events while preventing triple bookings.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of method calls with parameters. The first call is always the initialization of the MyCalendarTwo object, followed by calls to the book method.
Output: The output will be an array of boolean values for each call. The first call to the MyCalendarTwo constructor returns null. For each book method call, return true if the event can be booked without causing a triple booking, and false otherwise.
• Explanation: In this example, the first three events are successfully booked as they do not overlap more than twice. The fourth event fails as it causes a triple booking. The fifth event is booked because it only overlaps with one event at any time.
Approach: The approach involves using a data structure to track and manage overlapping events, ensuring no triple booking occurs.
Observations:
• We need a way to efficiently count overlapping events at any point in time.
• We can use a map to track the number of active events at any given time. This will allow us to quickly determine if adding a new event causes a triple booking.
Steps:
• 1. Use a map to store the start and end times of events.
• 2. For each booking, increment the count at the start time and decrement at the end time.
• 3. Traverse the map to check if the number of active events exceeds 2 at any time. If it does, reject the booking.
Empty Inputs:
• If no events are booked yet, any event can be booked.
Large Inputs:
• Ensure the solution efficiently handles up to 1000 booking attempts.
Special Values:
• Consider events with very close start and end times that could overlap very slightly.
Constraints:
• The solution must handle start and end times within the range of [0, 10^9].
public:MyCalendarTwo() {
}
boolbook(int start, int end) {
mp[start]++;
mp[end]--;
int bkd =0;
for(auto it =mp.begin(); it != mp.end(); it++) {
bkd += it->second;
if(bkd ==3) {
mp[start]--;
mp[end]++;
returnfalse;
}
}
returntrue;
}
};
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo* obj = new MyCalendarTwo();
* bool param_1 = obj->book(start,end);
1 : Method Declaration
public:
Access modifier specifying that the following methods are publicly accessible.
2 : Constructor
MyCalendarTwo() {
Constructor for the MyCalendarTwo class, initializing the object.
3 : Empty Block
Empty line for spacing, no code here.
4 : End Block
}
Closing bracket to end the constructor.
5 : Method Declaration
boolbook(int start, int end) {
Declaring the 'book' method, which checks if a new event can be booked.
6 : Update Map
mp[start]++;
Increments the count for the 'start' time in the map, indicating the start of an event.
7 : Update Map
mp[end]--;
Decrements the count for the 'end' time in the map, indicating the end of an event.
8 : Variable Declaration
int bkd =0;
Declares an integer variable 'bkd' to keep track of the number of overlapping events.
9 : ForLoop
for(auto it =mp.begin(); it != mp.end(); it++) {
Iterates over the events in the map to check the number of overlapping events.
10 : Update Variable
bkd += it->second;
Adds the value from the current map entry to 'bkd' to track the current overlap count.
11 : If Statement
if(bkd ==3) {
Checks if the number of overlapping events has reached 3 (i.e., more than 2 overlapping events).
12 : Update Map
mp[start]--;
Decrements the count for the 'start' time, effectively canceling the booking.
13 : Update Map
mp[end]++;
Increments the count for the 'end' time to reflect the cancellation.
14 : Return Statement
returnfalse;
Returns 'false' to indicate that the booking cannot be made due to too many overlapping events.
15 : Return Statement
returntrue;
Returns 'true' to indicate that the booking was successful.
Best Case: O(log N)
Average Case: O(log N)
Worst Case: O(N)
Description: In the worst case, we check all events for conflicts, making the time complexity O(N), where N is the number of events.
Best Case: O(N)
Worst Case: O(N)
Description: The space complexity is O(N) as we store the number of events in the calendar.
