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
1MyCalendar myCalendar = new MyCalendar();
2myCalendar.book(10, 20); // return True
3myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
4myCalendar.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
1class MyCalendar:
2 def __init__(self):
3 self.calendar = []
4
5 def book(self, start: int, end: int) -> bool:
6 left, right, idx = 0, len(self.calendar)-1, len(self.calendar)
7 while left <= right:
8 mid = (left + right) // 2
9 if self.calendar[mid][0] > start:
10 idx = mid
11 right = mid - 1
12 else:
13 left = mid + 1
14 # check if calendar[idx-1] or calendar[idx] overlaps with start and end
15 if (idx > 0 and self.calendar[idx-1][1] > start) or (idx < len(self.calendar) and self.calendar[idx][0] < end):
16 return False
17 self.calendar.insert(idx, (start, end))
18 return True
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
What are the most two important steps in writing a depth first search function? (Select 2)
Solution Implementation
Which type of traversal does breadth first search do?
How many ways can you arrange the three letters A, B and C?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
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
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.