Problem Statement

My Calendar I

We are building a calendar that never lets two events sit on top of each other. You call book(start, end) to add an event, where start is the time it begins and end is the time it ends. The book call returns true if the event fits without bumping into another event, and false if it would clash. One important rule: the end time is "exclusive", which means an event runs up to but not including its end. So an event from 10 to 20 actually fills the slots 10, 11, ... up to 19, and 20 is free. That is why an event ending at 20 and another starting at 20 do not collide. Two events clash (overlap) when one starts before the other ends AND ends after the other starts.

mediumIntervalsDesignIntervalsTime: O(n) · Space: O(n)

Signals to notice

book non-overlapping eventscheck if new event conflictssorted intervals

Brute force first

For each booking, check all existing bookings for overlap — total. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

Maintain a sorted list of intervals. For each new booking, binary search for the insertion point and check neighbors for overlap. over all operations. Or use a balanced BST (TreeMap). Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `ops: book(10,20), book(15,25), book(20,30)`

bookings=[] | book(10,20): no existing intervals to check -> append (10,20), return true
bookings=[(10,20)] | book(15,25): check (10,20): 15<20 and 25>10 -> overlap -> return false
bookings=[(10,20)] | book(20,30): check (10,20): 20<20 is false -> no overlap -> append (20,30), return true
bookings=[(10,20),(20,30)] | final outputs: [true, false, true]

What must stay true

Two intervals [s1,e1) and [s2,e2) overlap if and only if s1 < e2 AND s2 < e1. Checking only the neighboring intervals in sorted order is sufficient. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

book(start, end):
  for (s, e) in bookings:
    if start < e and end > s:   # overlap
      return false
  bookings.append((start, end))
  return true

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Checking all existing intervals — with a sorted structure, you only need to check the neighbors at the insertion point. The fix is usually to return to the meaning of each move, not just the steps themselves.

Intervals Pattern