729. My Calendar I
Problem Description
In this problem, you are tasked with creating a program that acts as a calendar. The primary function of this calendar is to ensure that when a new event is added, it doesn't clash with any existing events (a situation referred to as a "double booking"). An event is defined by a start time and an end time, which are represented by a pair of integers. These times create a half-open interval [start, end)
, meaning it includes the start time up to, but not including, the end time.
Your job is to implement a MyCalendar
class that will hold the events and has the following capabilities:
MyCalendar()
is a constructor that initializes the calendar object.book(int start, int end)
is a method that adds an event to the calendar if it does not conflict with any existing events. If the event can be added without causing a double booking, it returnstrue
; otherwise, it returnsfalse
and does not add the event.
The goal is to ensure that no two events overlap in time.
Intuition
The key to solving this problem is to efficiently determine whether the newly requested booking overlaps with any existing bookings. One way to approach this is by maintaining a sorted list of events, allowing for quick searches and insertions.
The intuition is to search for the correct location to insert a new event such that the list remains sorted. We must check two things:
- That the new event's start time does not conflict with the end time of the previous event.
- That the new event's end time does not conflict with the start time of the next event.
We can accomplish this by:
- Using the
sortedcontainers.SortedDict
class, which keeps keys in a sorted order. This allows us to quickly find the position where the new event could be inserted. - Applying the
bisect_right
method to find the index of the smallest event end that is greater than the new event's start time. - Checking if the new event's end time conflicts with the next event's start time in the sorted dictionary.
- If there is no conflict, we insert the new event into the "sorted" dictionary, with the end time as the key and the start time as the value.
- By keeping the dictionary sorted by the end time, this ensures that we can always quickly check for potential overlap with the immediately adjacent events in the sorted list of bookings.
The implementation of the book
method in our solution proceeds with this intuition, allowing for efficient booking operations. Each booking can be processed in logarithmic time with respect to the number of existing bookings, therefore making the solution scalable for a large number of events.
Learn more about Segment Tree and Binary Search patterns.
Solution Approach
The implementation of MyCalendar
relies on the sortedcontainers
Python library, which offers a SortedDict
data structure to maintain the events sorted by their end times. Here's a walkthrough of how the solution is implemented using this SortedDict
:
-
Initialization: When the
MyCalendar
class is instantiated, it initializes aSortedDict
in the constructor. ThisSortedDict
is stored in theself.sd
attribute of the class instances, ready to keep track of the booked events.1def __init__(self): 2 self.sd = SortedDict()
-
Booking an Event: The
book
method is where the logic to check for double bookings and add events takes place.-
First, we find the index (position) where the new event's end time would be inserted into the
SortedDict
. We use thebisect_right
method, which returns an index pointing to the first element in theSortedDict
's values that is greater than thestart
time.1idx = self.sd.bisect_right(start)
-
Now, we need to ensure that the new event does not conflict with the next event in the
SortedDict
. We check if the found index is within the bounds of theSortedDict
and if the new event'send
time is greater than the start time of the event at that index.1if idx < len(self.sd) and end > self.sd.values()[idx]: 2 return False
-
If there is no conflict, it means the new event does not cause a double booking, and we insert it into the dictionary. Here, the event's
end
time is used as the key and thestart
time as the value. This ensures the events are sorted by their end times.1self.sd[end] = start
-
After successfully adding the event without conflicts, the method returns
True
. -
If at any point we detect an overlap (a potential double booking), we return
False
without adding the event.
1def book(self, start: int, end: int) -> bool: 2 idx = self.sd.bisect_right(start) 3 if idx < len(self.sd) and end > self.sd.values()[idx]: 4 return False 5 self.sd[end] = start 6 return True
-
The book
method performs at most two key operations: finding where to insert and actually inserting the event. Both operations are efficient due to the nature of the SortedDict
, which maintains the order of keys and allows for binary search insertions and lookups. This is how the provided solution ensures no double bookings occur while adding events to the MyCalendar
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a small example to illustrate the solution approach.
Imagine we have a MyCalendar
instance and we want to book two events. The first event is from time 10 to 20, and the second event is from time 15 to 25.
When we try to book the first event:
- We initialize our
MyCalendar
and its underlyingSortedDict
, currently empty. - We attempt to book an event with
start=10
andend=20
. self.sd.bisect_right(10)
will return 0 since there are no keys greater than 10 (as the dictionary is empty).- Since the index 0 is within bounds and there are no events, there are no conflicts.
- We add the event to the
SortedDict
with key 20 and value 10.
Now, MyCalendar
looks like this:
self.sd
contains{20: 10}
When we try to book the second event:
- We attempt to book the second event with
start=15
andend=25
. self.sd.bisect_right(15)
will return index 0 since 20 is the first key greater than 15.- We check if
idx
is within bounds and ifend
(25) is greater than the start time of the event at index 0 (which is 10). Since 25 is indeed greater than 10, there is a potential overlap with the existing event. - Since end time 25 of the new event is greater than start time 10 of the existing event, which would result in a double booking, we return
False
.
Thus, the attempt to book an event from time 15 to 25 fails, preserving the non-overlapping constraint of the calendar. The SortedDict
remains unchanged with the single event {20: 10}
and no double booking occurs.
Solution Implementation
1from sortedcontainers import SortedDict
2
3class MyCalendar:
4 def __init__(self):
5 # Create a sorted dictionary to store the end time of each event
6 # as the key and the start time as the value
7 self.sorted_events = SortedDict()
8
9 def book(self, start: int, end: int) -> bool:
10 """
11 Attempts to book an event in the calendar based on the provided start and end times.
12 Returns True if the event can be booked (doesn't overlap with existing events);
13 otherwise returns False.
14
15 :param start: The start time of the event
16 :param end: The end time of the event
17 :return: Boolean indicating whether the event was successfully booked
18 """
19 # Find the index of the first event that ends after the requested start time
20 next_event_index = self.sorted_events.bisect_right(start)
21
22 # Check if there is a conflict with the next event:
23 # - If next_event_index is within the bounds of the sorted dictionary,
24 # check if the requested end time is greater than the start time of the next event.
25 if next_event_index < len(self.sorted_events) and end > self.sorted_events.values()[next_event_index]:
26 return False # Event cannot be booked due to overlap
27
28 # If there is no conflict, insert the new event into the sorted dictionary.
29 self.sorted_events[end] = start
30 return True # Event booked successfully
31
32# Example of how to instantiate the MyCalendar class and book events:
33# calendar = MyCalendar()
34# is_booked = calendar.book(start, end)
35# print(is_booked)
36
1import java.util.Map;
2import java.util.TreeMap;
3
4// The class MyCalendar is designed to store bookings as intervals.
5// It uses a TreeMap to keep the intervals sorted by start time.
6class MyCalendar {
7
8 // Using TreeMap to maintain the intervals sorted by the start key.
9 private final TreeMap<Integer, Integer> calendar;
10
11 // Constructor initializes the TreeMap.
12 public MyCalendar() {
13 calendar = new TreeMap<>();
14 }
15
16 /**
17 * Tries to book an interval from start to end.
18 * @param start the starting time of the interval
19 * @param end the ending time of the interval
20 * @return true if the booking does not conflict with existing bookings, false otherwise
21 */
22 public boolean book(int start, int end) {
23 // Retrieves the maximum entry whose key is less than or equal to start.
24 Map.Entry<Integer, Integer> floorEntry = calendar.floorEntry(start);
25
26 // If there is an overlap with the previous interval, return false.
27 if (floorEntry != null && floorEntry.getValue() > start) {
28 return false;
29 }
30
31 // Retrieves the minimum entry whose key is greater than or equal to start.
32 Map.Entry<Integer, Integer> ceilingEntry = calendar.ceilingEntry(start);
33
34 // If there is an overlap with the next interval, return false.
35 if (ceilingEntry != null && ceilingEntry.getKey() < end) {
36 return false;
37 }
38
39 // If there is no overlap, add the interval to the TreeMap and return true.
40 calendar.put(start, end);
41 return true;
42 }
43}
44
45// Usage example:
46// MyCalendar obj = new MyCalendar();
47// boolean isBooked = obj.book(start, end);
48
1#include <map>
2using namespace std;
3
4class MyCalendar {
5private:
6 // map to keep track of event starts (+1) and ends (-1)
7 map<int, int> events;
8
9public:
10 // Constructor initializes the MyCalendar object
11 MyCalendar() {
12 }
13
14 /* Function to book a new event from 'start' to 'end' time.
15 Returns true if the event can be booked without conflicts,
16 otherwise returns false. */
17 bool book(int start, int end) {
18 // Increment the count for the start time of the new event
19 events[start]++;
20 // Decrement the count for the end time of the new event
21 events[end]--;
22
23 int currentEvents = 0; // counter for overlapping events
24
25 // Iterate through all time points in the map
26 for (auto& keyValue : events) {
27 // Add up the values to check for overlaps
28 currentEvents += keyValue.second;
29
30 // If more than one event is happening at the same time, revert changes and return false
31 if (currentEvents > 1) {
32 events[start]--;
33 events[end]++;
34 return false;
35 }
36 }
37
38 // No overlap found, event is successfully booked
39 return true;
40 }
41};
42
43// Example usage:
44// MyCalendar* calendar = new MyCalendar();
45// bool canBook = calendar->book(start,end);
46
1// A global array to keep track of booked time slots as an array of start-end pairs.
2let calendar: number[][] = [];
3
4/**
5 * Attempts to book a new event in the calendar.
6 *
7 * @param {number} start The start time of the event.
8 * @param {number} end The end time of the event.
9 * @return {boolean} True if the event can be successfully booked without conflicts; otherwise, false.
10 */
11function book(start: number, end: number): boolean {
12 // Iterate through each already booked event in the calendar.
13 for (const item of calendar) {
14 // If the new event overlaps with an existing event, return false.
15 if (end > item[0] && start < item[1]) {
16 return false;
17 }
18 }
19 // If there is no overlap, add the new event to the calendar and return true.
20 calendar.push([start, end]);
21 return true;
22}
23
Time and Space Complexity
The provided code implements a class MyCalendar
that stores the start time of the events as values and the end time as keys in a SortedDict
. When a new event is booked, it checks if there is any overlap with existing events and then stores the event in the SortedDict
if there is no overlap.
Time Complexity
-
__init__
: The constructor simply creates a newSortedDict
, which is an operation takingO(1)
time. -
book
: This method involves two main actions. First, it performs a binary search to find the right position where the new event should be inserted. Thebisect_right
method inSortedDict
runs inO(log n)
time wheren
is the number of keys in the dictionary. Secondly, the code inserts the new(end, start)
pair into the dictionary. Inserting into aSortedDict
also takesO(log n)
time. Therefore, the overall time complexity for eachbook
operation isO(log n)
.
Space Complexity
The space complexity of the code is mainly dictated by the storage requirements of the SortedDict
.
- With no events booked, the space complexity is
O(1)
as only an emptySortedDict
is maintained. - As events are added, the space complexity grows linearly with the number of non-overlapping events stored. Therefore, in the worst-case scenario, where the calendar has
n
non-overlapping events, the space complexity would beO(n)
.
Overall, the space complexity of the MyCalendar
data structure is O(n)
where n
is the number of non-overlapping events booked in the calendar.
Learn more about how to find time and space complexity quickly using problem constraints.
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
14
1public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
1function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.