This content originally appeared on DEV Community and was authored by seanpgallivan
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.
Instead, we can do better by using 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: O(N) where N is the length of the linked list
- Space Complexity: O(N) for the linked list
Javascript Code:
(Jump to: Problem Description || Solution Idea)
class MyCalendar {
constructor() {
this.head = {start: -1, end: -1, next: {start: Infinity, end:Infinity}}
}
book = function(start, end) {
let curr = this.head, last
while (curr.start < start)
last = curr, curr = curr.next
if (last.end > start || curr.start < end)
return false
last.next = {start: start, end: end, next: curr}
return true
};
}
Python Code:
(Jump to: Problem Description || Solution Idea)
class MyCalendar:
def __init__(self):
self.head = {'start': -1, 'end': -1, 'next': {'start': float('inf'), 'end': float('inf')}}
def book(self, start: int, end: int) -> bool:
curr = self.head
while curr['start'] < start:
last, curr = curr, curr['next']
if last['end'] > start or curr['start'] < end:
return False
last['next'] = {'start': start, 'end': end, 'next': curr}
return True
Java Code:
(Jump to: Problem Description || Solution Idea)
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 head;
public MyCalendar() {
ListNode tail = new ListNode(Integer.MAX_VALUE, Integer.MAX_VALUE, null);
head = new ListNode(-1, -1, tail);
}
public boolean book(int start, int end) {
ListNode curr = head, last = head;
while (curr.start < start) {
last = curr;
curr = curr.next;
}
if (last.end > start || curr.start < end)
return false;
last.next = new ListNode(start, end, curr);
return true;
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
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);
head = new LNode(-1, -1, tail);
}
bool book(int start, int end) {
LNode* curr = head, *last = head;
while (curr->start < start)
last = curr, curr = curr->next;
if (last->end > start || curr->start < end)
return false;
last->next = new LNode(start, end, curr);
return true;
}
private:
LNode* head;
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-06-10T09:04:50+00:00) Solution: My Calendar I. Retrieved from https://www.scien.cx/2021/06/10/solution-my-calendar-i/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.