Facebook Pixel

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) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false 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 to book.

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 
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

We want to store the bookings in a sorted array called calendar, each booking is represented by the pair (start, end) indicating its start and end time.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More