My Calendar I
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 start
and end
that represents a booking on the half-open interval [start, end)
, the range of real numbers x
such that start <= x < end
.
Implement the MyCalendar
class:
MyCalendar()
Initializes the calendar object.boolean book(int start, int end)
Returnstrue
if the event can be added to the calendar successfully without causing a double booking. Otherwise, returnfalse
and do not add the event to the calendar.
Example 1:
Input ["MyCalendar", "book", "book", "book"] [[], [10, 20], [15, 25], [20, 30]] Output [null, true, false, true]
Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.
Constraints:
0 <= start < end <= 109
- At most
1000
calls will be made tobook
.
Solution
To implement the booking behaviour, we will use binary search to find a potential insertion index, then check whether the new booking can be
actually scheduled into our calendar by checking whether the new booking overlaps with calendar[idx-1]
and calendar[idx]
.
Implementation
class MyCalendar:
def __init__(self):
self.calendar = []
def book(self, start: int, end: int) -> bool:
left, right, idx = 0, len(self.calendar)-1, len(self.calendar)
while left <= right:
mid = (left + right) // 2
if self.calendar[mid][0] > start:
idx = mid
right = mid - 1
else:
left = mid + 1
# check if calendar[idx-1] or calendar[idx] overlaps with start and end
if (idx > 0 and self.calendar[idx-1][1] > start) or (idx < len(self.calendar) and self.calendar[idx][0] < end):
return False
self.calendar.insert(idx, (start, end))
return True
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorHow does quick sort divide the problem into subproblems?
Recommended Readings
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
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!