My Calendar II
Problem Description
You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.
A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).
The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < endTime.
Implement the MyCalendarTwo class:
1. MyCalendarTwo() Initializes the calendar object.
2. boolean book(int startTime, int endTime) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.
What is a triple booking?
Triple booking in context to this problem statement says that there must not be three overlapping events at a particular period of time.
Examples
Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]
Explanation
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // return True, The event can be booked.
myCalendarTwo.book(50, 60); // return True, The event can be booked.
myCalendarTwo.book(10, 40); // return True, The event can be double booked.
myCalendarTwo.book(5, 15); // return False, The event cannot be booked, because it would result in a triple booking.
myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked.
myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.
Constraints
- 0 <= start < end <= 10^9
- At most 1000 calls will be made to book.
The problem statement is a design based task which asks us that no more than two meetings can happen during a period of time. Let's implement the first intuitive thought that is by iterating the intervals over and over again and then returning the result !!
Brute Force Approach
Intuition
Imagine we are given a task to tell our client whether he/she can book a particular event for a certain time period. But, we need to make sure that no more than two events should overlap. If there are more than two events overlapping at the same period of time, we will alert our client not to book that particular event.
How are we going to do that job??
Simple, let's maintain a register , each time we are asked to schedule an event between a time period say startTime to endTime. We will add 1 cross mark in the register from startTime till endTime. If the registers between these intervals have no or 1 cross mark, we can tell our client that we can schedule the event at that particular time. If we see 2 cross marks in a particular interval, we have to cancel the event.
But how we gonna code it?
We represent the registers as indices of an array/vector/list. Whenever the "MyCalendarTwo" constructor is called, we initialize the array with initial values as 0. Why 0 and not -1 ? Because, there can't be negative number of meetings in a particular time period.
And whenever the book(int startTime , int endTime) is called we will run a loop from startTime to endTime and add +1 to the indices.
But !!
If we see the constraints that the end time can go up to 10^9, can we initialize any data-structure to 1000000001?
No, it's not possible. The first intuitive thought will give us a memory limit exceeded error. Our brute force will not be accepted to the problem statement !!
If we observe clearly, Memory Limit Exceeded is not the only concern. Have we observed that repetitive loops in the book() function may rise to O(n^2) in the worst case which is too high for constraints given in the question.
What's next ?? We have to analyse the slower part of our brute force approach and make it optimize, let's figure it out together !!
Optimal Approach
Intuition
Now let's think about the same problem statement with a different scenario.
We’ll imagine that time is like a long road. Each event is like a car that gets on the road at startTime and leaves at endTime. Our goal is to track how many cars (events) are on the road at the same time. If more than two cars are on the road together at any point, we can’t let another one join.
But shall we still follow the brute force approach to monitor each car until it leaves the highway?
No, we have to think for a smarter approach.
Let's use a record to store the startTime of a car when it enters the highway and the endTime when it leaves the highway.
In other words, we will maintain a record where we will write startTime → 1 and endTime → -1. This information tells us that at startTime , a car entered the highway and at endTime a car leaves the highway. This means the car was on the highway from startTime to endTime.
This is a smart play because now we are monitoring the highways only when the car enters and leaves.
How is it better than the brute force ?
In brute force approach it took O(n^2) to track the events and now we are taking constant runtime to mark the records. Isn't it faster??
Yes !! much faster !!
But now there will be many such records with startTime as 1 and endTime as -1. (startTime and endTime can lie anywhere between 0 to 10^9).
How to figure out that there are no more than two cars on the highway at a particular moment ?
Recall, that we used startTime -> 1 ,which meant 1 car entered the highway. What if we maintain the records in a sorted manner and each time we will iterate over the records and then count and know how many cars are there in the highway?
Wait, this means we are using a data-structure that maps a key to a value and stores in a sorted way?
Yes, it's a Map. But this time we will be using a map which stores the information in sorted manner. So, we are using a TreeMap(java) , ordered_map(C++),etc.
Once, we are done marking i.e. we have entered the information to the maps, we will sweep with the values by maintaining a running sum.
Why running sum?? A running sum will ensure that whenever we encounter startTime -> 1, we will add 1 representing a car entered the highway and will substract 1 when we encounter endTime -> -1.
The algorithm we followed is the line sweep algorithm.
So, whenever the running sum reaches 3, we can say that the booking is not possible. Let's see how we can implement this to our coding part.
Approach
For MyCalendarTwo(): initialize an ordered_map, TreeMap
For book(int startTime , int endTime):
Add start and end times to the map:
- At startTime, increment the value by +1 (event starts).
- At endTime, decrement the value by -1 (event ends).
Sweep through the map to check for overlaps: Initialize sum =0 to track ongoing events.
For each time point in the map (in sorted order):
- Add the value at that time to sum.
- If sum exceeds 2, it means more than two events overlap: Undo the changes at startTime and endTime by reversing the increment/decrement.
Return false (booking fails).
If no triple booking is found, return true.
Dry-Run
Example Events to Book :Book(10, 20), Book(15, 25), Book(20, 30), Book(18, 22)
Initial Setup: map is empty: {}
Book(10, 20)
Add +1 at 10 and -1 at 20.
map becomes: { 10: 1, 20: -1 }
Sweep through the map:
- sum = 0 initially.
- At 10: sum += 1 → sum = 1
- At 20: sum += (-1) → sum = 0
- No triple booking (max sum = 1).
- Return true (booking successful).
Book(15, 25)
Add +1 at 15 and -1 at 25.
map becomes: { 10: 1, 15: 1, 20: -1, 25: -1 }
Sweep through the map:
- At 10: sum = 1
- At 15: sum = 2
- At 20: sum = 1
- At 25: sum = 0
- No triple booking (max sum = 2).
- Return true.
Book(20, 30)
Add +1 at 20 and -1 at 30.
map becomes: { 10: 1, 15: 1, 20: 0, 25: -1, 30: -1 }
Sweep through the map:
- At 10: sum = 1
- At 15: sum = 2
- At 20: sum = 2
- At 25: sum = 1
- At 30: sum = 0
- No triple booking.
- Return true.
Book(18, 22) ⟵ Potential Triple Booking
Add +1 at 18 and -1 at 22.
map becomes: {8: 1, 20: 0, 22: -1, 25: -1, 30: -1 }
Sweep through the map:
- At 10: sum = 1
- At 15: sum = 2
- At 18: sum = 3 ⟵ Triple booking detected!
- Undo the booking:
Subtract -1 at 18 → map[18] = 0
Add +1 at 22 → map[22] = 0 - map after undo: { 10: 1, 15: 1, 20: 0, 25: -1, 30: -1 }
- Return false (booking fails).
Final State of map :{ 10: 1, 15: 1, 20: 0, 25: -1, 30: -1 }
Events booked successfully:
(10, 20), (15, 25),(20, 30)
Failed event: (18, 22)
Optimal Code in all Languages
1. C++ Try on Compiler
class MyCalendarTwo {
public:
// Map to store the start and end times with booking counts
map<int, int> myMap;
// Constructor to initialize the map
MyCalendarTwo() {}
// Method to book an event from startTime to endTime
bool book(int startTime, int endTime) {
// Add the start time to the map with +1
myMap[startTime]++;
// Add the end time to the map with -1
myMap[endTime]--;
// Variable to track the sum of overlapping events at any point
int sum = 0;
// Iterate over the sorted entries in the map
for (auto& entry : myMap) {
// Update the sum by adding the current event count (either +1 or -1)
sum += entry.second;
// If the sum exceeds 2, it means there is a triple booking
if (sum > 2) {
// Rollback the booking by decreasing the count at start and end times
myMap[startTime]--;
myMap[endTime]++;
// Return false as we cannot allow triple bookings
return false;
}
}
// Return true as the booking was successful
return true;
}
};2. Java Try on Compiler
public class MyCalendarTwo {
// TreeMap to store the start and end times with booking counts
public Map<Integer, Integer> map;
// Constructor to initialize the TreeMap
public MyCalendarTwo() {
map = new TreeMap<>();
}
// Method to book an event from startTime to endTime
public boolean book(int startTime, int endTime) {
// Add the start time to the map with +1 (indicating the start of an event)
map.put(startTime, map.getOrDefault(startTime, 0) + 1);
// Add the end time to the map with -1 (indicating the end of an event)
map.put(endTime, map.getOrDefault(endTime, 0) - 1);
// Variable to track the sum of overlapping events at any point
int sum = 0;
// Iterate over the sorted entries in the map
for (var entry : map.entrySet()) {
// Update the sum by adding the current event count (either +1 or -1)
sum += entry.getValue();
// If the sum exceeds 2, it means there is a triple booking
if (sum > 2) {
// Rollback the booking by decreasing the count at start and end times
map.put(startTime, map.get(startTime) - 1);
map.put(endTime, map.get(endTime) + 1);
// Return false as we cannot allow triple bookings
return false;
}
}
// Return true as the booking was successful
return true;
}
}
3. Python Try on Compiler
class MyCalendarTwo:
def __init__(self):
self.map = {}
def book(self, startTime: int, endTime: int) -> bool:
# Add the start time to the map with +1 (indicating the start of an event)
self.map[startTime] = self.map.get(startTime, 0) + 1
# Add the end time to the map with -1 (indicating the end of an event)
self.map[endTime] = self.map.get(endTime, 0) - 1
# Variable to track the sum of overlapping events at any point
sum = 0
# Iterate over the sorted entries in the map
for time in sorted(self.map.keys()):
# Update the sum by adding the current event count (either +1 or -1)
sum += self.map[time]
# If the sum exceeds 2, it means there is a triple booking
if sum > 2:
# Rollback the booking by decreasing the count at start and end times
self.map[startTime] -= 1
self.map[endTime] += 1
# Return false as we cannot allow triple bookings
return False
# Return true as the booking was successful
return True
4. JavaScript Try on Compiler
var MyCalendarTwo = function() {
this.map = new Map();
};
MyCalendarTwo.prototype.book = function(startTime, endTime) {
// Add the start time to the map with +1
this.map.set(startTime, (this.map.get(startTime) || 0) + 1);
// Add the end time to the map with -1
this.map.set(endTime, (this.map.get(endTime) || 0) - 1);
// Variable to track the sum of overlapping events at any point
let sum = 0;
// Iterate over the sorted entries in the map
for (let [time, count] of [...this.map.entries()].sort((a, b) => a[0] - b[0])) {
// Update the sum by adding the current event count (either +1 or -1)
sum += count;
// If the sum exceeds 2, it means there is a triple booking
if (sum > 2) {
// Rollback the booking by decreasing the count at start and end times
this.map.set(startTime, this.map.get(startTime) - 1);
this.map.set(endTime, this.map.get(endTime) + 1);
// Return false as we cannot allow triple bookings
return false;
}
}
// Return true as the booking was successful
return true;
};
Time Complexity: O(n)
The main operation in the book method is the iteration over the entries in the map .
Insertion into the map: Each map operation is O(log n) where n is the number of unique time points (i.e., the size of the map).
Iterating over the map entries: The iteration over the entries in the map takes O(n), where n is the number of unique keys (time points) in the map.
Thus, the overall time complexity of the book method is dominated by the iteration over the map and the insertion into the map, which is:
O(log n + n), where N is the number of unique time points in the map. In the worst case, this simplifies to O(n) because the iteration can process all the unique time points.
Space Complexity: O(n)
Auxiliary Space Complexity
The auxiliary space complexity refers to the space used by the algorithm, excluding the space used by the input.
- The space used by the map is directly related to the number of unique time points stored .
- The variable sum is a simple integer used during the iteration, and its space usage is constant: O(1).
Thus, the auxiliary space complexity is O(n), where n is the number of unique time points in the map.
Total Space Complexity
The total space complexity includes the space used by the map and any additional space used by the algorithm.
- The map stores key-value pairs for each unique start and end time, so the total space complexity is O(n), where n is the number of unique time points.
- Auxiliary space: O(n)
Thus, the total space complexity is also O(n) + O(n) = O(2n) = O(n).
Learning Tip
You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.
A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).
The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < endTime.
Implement the MyCalendar class:
- MyCalendar() Initializes the calendar object.
- boolean book(int startTime, int endTime) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.
A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.)
You are given some events [startTime, endTime), after each given event, return an integer k representing the maximum k-booking between all the previous events.
Implement the MyCalendarThree class:
- MyCalendarThree() Initializes the object.
- int book(int startTime, int endTime) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.