DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

My Calendar I

mediumIntervals Must-doGoogle SRE

Problem statement

Design a class MyCalendar that accepts bookings only when they do not clash with an existing one.

  • MyCalendar() creates an empty calendar.
  • book(start, end) tries to add an event covering the half-open range [start, end): it includes start but not end. If the event overlaps any event already in the calendar, return false and do not add it. Otherwise add it and return true.

Because ranges are half-open, an event ending at 20 and another starting at 20 do not overlap.

Examples

Example 1

Input: book(10, 20) book(15, 25) book(20, 30)

Output: true false true

Explanation: [15, 25) overlaps [10, 20). [20, 30) starts exactly where [10, 20) ends, which is allowed.

Example 2

Input: book(5, 10) book(1, 6) book(1, 5)

Output: true false true

Explanation: [1, 6) overlaps [5, 10) on 5. [1, 5) stops just before it.

Hints

Approach

Keep bookings ordered by start time and only check the two neighbours.

  1. Find where start would go among the sorted start times.
  2. The booking just before that position must end at or before start (prev_end <= start).
  3. The booking just after it must start at or after end (next_start >= end).
  4. If both hold, insert the booking at that position and return true; otherwise return false.

Accepted bookings never overlap, so if the two neighbours are clear, nothing further away can clash. In Java, a TreeMap from start to end gives floorKey/ceilingKey and insertion in O(log n). Python has no built-in balanced tree, so the Python version uses bisect on sorted lists: the search is O(log n), but list.insert shifts elements and is O(n) in the worst case.

ComplexityTime O(log n) per book (TreeMap)Space O(n)
Python
from bisect import bisect_right
class MyCalendar:
def __init__(self):
self.starts = [] # sorted start times
self.ends = [] # ends, parallel to starts
def book(self, start: int, end: int) -> bool:
i = bisect_right(self.starts, start)
if i > 0 and self.ends[i - 1] > start: # clashes with the previous booking
return False
if i < len(self.starts) and self.starts[i] < end: # clashes with the next booking
return False
self.starts.insert(i, start)
self.ends.insert(i, end)
return True

Follow-up questions

  • Allow each time to be double-booked but never triple-booked.
  • Return the maximum number of events overlapping at any moment after each booking.

Frequently asked questions

It is a reservation system for any exclusive resource: a shared staging environment, a lab device, a deploy lock, or a change window. "Reject the request if it clashes, otherwise record it" is the core of all of them.

With [start, end), back-to-back bookings like 10-20 and 20-30 are allowed, which matches how calendars work. The overlap test uses strict < on both sides for that reason. With closed ranges you would use <=.

The lookup is O(log n), but inserting into the middle of a list is O(n) because elements shift. It is fast in practice for thousands of bookings. For a true O(log n) insert in Python, use a balanced tree or the third-party sortedcontainers.SortedList.