This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #729 (Medium): My Calendar I
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
Implement a
MyCalendarclass to store your events. A new event can be added if adding the event will not cause a double booking.Your class will have the method,
book(int start, int end). Formally, this represents a booking on the half open interval[start, end), the range of real numbersxsuch thatstart <= x < end.A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)
For each call to the method
MyCalendar.book, returntrueif the event can be added to the calendar successfully without causing a double booking. Otherwise, returnfalseand do not add the event to the calendar.Your class will be called like this:
MyCalendar cal = new MyCalendar();MyCalendar.book(start, end)
Examples:
Example 1: Input: MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
Explanation: The first event can be booked.
The second can't because time 15 is already booked by another event.
The third event can be booked, as the first event takes every time less than 20, but not including 20.
Constraints:
- The number of calls to
MyCalendar.bookper test case will be at most1000.- In calls to
MyCalendar.book(start, end),startandendare integers in the range[0, 10^9].
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
Since the bookings are not allowed to overlap, we'll naturally need to keep the data sorted in some way so that we can find the proper insertion position of each new booking, and to check for the validity of the booking.
The naive solution here would be to use an array and resort it each time, at a time complexity of O(N * log N). Alternately, we could use a binary search to find the right position, then insert the booking at that position, but that would take O(log N) time for the binary search and another O(N) time for the insertion.
(Important Note: Apparently, each of the four languages except Javascript has a sorted data structure based on a red-black tree structure which allows for insertion in only O(log N) time, rather than the O(N) time it would take for a standard array insertion. This, combined with the O(log N) time for the binary search makes this approach faster than a linked list approach. See the updated section below for the explanation.)
Python, Java, & C++:
Python, Java, and C++ allow for a sorted data structure with only a O(log N) insertion. In this approach, we first use a binary search function to find the proper insertion position, then compare the start and end of the new booking to the existing calendar entries to check for the validity of the new booking.
To avoid having to compare more than one calender entry for validation (as finding another entry might take another O(log N) time), we can store the entries in reverse order in calendar ({end, start}), then find the upper bound of the booking using the proper order ({start, end}).
Let's consider a booking gap that looks like this:
|---------| |---------|
If we're comparing start vs start in our binary search, we could end up with the following scenarios:
S---------| S---------|
<-----------------------> // binary search range
S---------| // possibility #1
S---------| // possibility #2
S---------| // possibility #3
This means that we'll have to access both surrounding bookings to check if the new booking clears both the previous booking's end and the next booking's start. If, instead, we store the bookings with start and end flipped, the binary search will automatically clear the previous booking's end, which means those three scenarios shift to this:
|---------E |---------E
<-----------------------> // binary search range
S---------| // possibility #1
S---------| // possibility #2
S---------| // possibility #3
This means that we only have to access the booking returned by the binary search, saving us the O(log N) time for the second lookup, as well as only requiring a single conditional check (new.end <= next.start), rather than two.
If the booking is invalid, we can return false, otherwise we can insert the new booking into calendar (in reverse order) and then return true. We can also insert a tail booking upon the calendar initialization to make the comparisons easier.
Javascript:
For Javascript, we can use a linked list approach, as searching the linked list will only be O(N) time and the insertion will only be O(1) time. We should start by defining our empty bookings list (head) with a head node and a tail node as bookends for the booking data.
For the book function, we will then iterate through the linked list until we find the booking that begins after our attempted booking start (curr). We should also remember to keep track of the last node, as well, so that we can stitch the new booking into the list.
Once we've located the proper node, we should check to see if the new booking will overlap, and return false if it does. Otherwise, we should create our new node, and insert it between last and curr, then return true.
-
Time Complexity:
- single booking w/ sorted tree: O(log N) where N is the length of the calendar
- single booking w/ linked list: O(N)
- complete series w/ sorted tree: O(N * log N)
- complete series w/ linked list: O(N^2)
- Space Complexity: O(N) for the calendar
Javascript Code:
(Jump to: Problem Description || Solution Idea)
w/ Linked List:
class MyCalendar {
constructor() {
this.calendar = {start: -1, end: -1, next: {start: Infinity, end: Infinity}}
}
book = function(start, end) {
let curr = this.calendar, last = curr
while (start >= curr.end)
last = curr, curr = curr.next
if (curr.start < end)
return false
last.next = {start: start, end: end, next: curr}
return true
};
}
Python Code:
(Jump to: Problem Description || Solution Idea)
w/ SortedDict:
from sortedcontainers import SortedDict
class MyCalendar:
def __init__(self):
self.calendar = SortedDict({float('inf'):float('inf')})
def book(self, start: int, end: int) -> bool:
ix = self.calendar.bisect_right(start)
k,v = self.calendar.peekitem(ix)
res = end <= v
if res: self.calendar[end] = start
return res
w/ Linked List:
class MyCalendar:
def __init__(self):
self.calendar = {'start': -1, 'end': -1, 'next': {'start': float('inf'), 'end': float('inf')}}
def book(self, start: int, end: int) -> bool:
curr = self.calendar
while start >= curr['end']:
last, curr = curr, curr['next']
if curr['start'] < end:
return False
last['next'] = {'start': start, 'end': end, 'next': curr}
return True
Java Code:
(Jump to: Problem Description || Solution Idea)
w/ TreeMap:
class MyCalendar {
TreeMap<Integer,Integer> calendar = new TreeMap<>();
public MyCalendar() {
calendar.put(Integer.MAX_VALUE, Integer.MAX_VALUE);
}
public boolean book(int start, int end) {
Map.Entry<Integer,Integer> pair = calendar.higherEntry(start);
boolean res = end <= pair.getValue();
if (res) calendar.put(end, start);
return res;
}
}
w/ Linked List:
class ListNode {
public int start, end;
public ListNode next;
public ListNode(int s, int e, ListNode n) {
start = s;
end = e;
next = n;
}
}
class MyCalendar {
ListNode calendar;
public MyCalendar() {
ListNode tail = new ListNode(Integer.MAX_VALUE, Integer.MAX_VALUE, null);
calendar = new ListNode(-1, -1, tail);
}
public boolean book(int start, int end) {
ListNode curr = calendar, last = curr;
while (start >= curr.end) {
last = curr;
curr = curr.next;
}
if (curr.start < end)
return false;
last.next = new ListNode(start, end, curr);
return true;
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
w/ Set:
class MyCalendar {
public:
set<pair<int, int>> calendar = {{INT_MAX, INT_MAX}};
bool book(int start, int end) {
auto pair = calendar.upper_bound({start, end});
bool res = end <= pair->second;
if (res) calendar.insert({end, start});
return res;
}
};
w/ Linked List:
struct LNode {
public:
int start, end;
LNode* next;
LNode(int s, int e, LNode* n) {
start = s;
end = e;
next = n;
}
};
class MyCalendar {
public:
MyCalendar() {
LNode* tail = new LNode(INT_MAX, INT_MAX, nullptr);
calendar = new LNode(-1, -1, tail);
}
bool book(int start, int end) {
LNode* curr = calendar, *last = curr;
while (start >= curr->end)
last = curr, curr = curr->next;
if (curr->start < end)
return false;
last->next = new LNode(start, end, curr);
return true;
}
private:
LNode* calendar;
};
Top comments (2)
Thanks for this amazing solution
I've just updated the solution with an even better approach for Python, Java, and C++!
I missed this solution approach initially due to the fact that Javascript is my primary language.