My Calendar I

Medium

LeetCode ↗

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.

Explain Idea

Explanation

Keep calendar sorted by start time. For a new booking [start, end), we first use binary search to find the first existing booking whose start time is greater than start. Call that position idx. If we insert at idx, only two neighbors can conflict: the booking just before it (calendar[idx - 1]) and the booking at idx.

The overlap checks come directly from half-open intervals: if idx > 0 and calendar[idx - 1][1] > start, the previous booking extends into the new one, so reject. if idx < len(calendar) and calendar[idx][0] < end, the next booking starts before the new one ends, so reject. If neither condition holds, there is no overlap, so we insert at idx and return True.

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

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 5-minute evaluator for a personalized learning plan!

Start Evaluator

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False