AlgoMaster Logo

My Calendar I

Last Updated: April 3, 2026

medium
4 min read

Understanding the Problem

We need to build a calendar system that accepts or rejects event bookings. Each event occupies a half-open interval [start, end), meaning the event includes the start time but excludes the end time. This is the standard convention for time intervals because it makes adjacent events seamless. An event ending at 20 and another starting at 20 do not overlap.

The core challenge is detecting overlaps. Two intervals [s1, e1) and [s2, e2) overlap if and only if s1 < e2 AND s2 < e1. If either condition fails, the intervals are disjoint. This overlap condition is the foundation for every approach we'll discuss.

So the problem reduces to: maintain a collection of non-overlapping intervals. For each new interval, check if it conflicts with any existing one. If not, add it. If it does, reject it.

Key Constraints:

  • 0 <= start < end <= 10^9 -> The interval endpoints can be huge, so we can't allocate an array indexed by time. We need to store intervals explicitly.
  • At most 1000 calls to book -> With n up to 1000, even an O(n) per call solution (O(n^2) total) is fine. But an O(log n) approach is more interesting and worth knowing for follow-ups.

Approach 1: Brute Force (Linear Scan)

Intuition

The most natural approach: keep a list of all booked events. When a new booking comes in, check it against every existing event for overlaps. If none overlap, add the new event to the list.

Two intervals [s1, e1) and [s2, e2) overlap when s1 < e2 AND s2 < e1. Think of it this way: the intervals are disjoint only if one ends before the other starts. So they overlap unless e1 <= s2 (first ends before second starts) or e2 <= s1 (second ends before first starts). Flipping that gives us the overlap condition.

Algorithm

  1. Maintain a list of (start, end) pairs representing booked events.
  2. For each new book(start, end) call, iterate through all existing events.
  3. For each existing event (s, e), check if start < e AND s < end. If both are true, there's an overlap, so return false.
  4. If no overlap is found with any existing event, add (start, end) to the list and return true.

Example Walkthrough

1book(10, 20): bookings is empty, no events to check
[]
1/6

Code

For each new booking, we scan through every existing event. Most of those comparisons are wasted since most events are nowhere near the new one. What if we kept the events sorted so we could jump directly to the ones that might actually overlap?

Approach 2: Sorted List with Binary Search

Intuition

Here's the key insight: if we keep our bookings sorted by start time, we don't need to check every single one. A new interval [start, end) can only overlap with its immediate neighbors in the sorted order. Specifically, we need to find where the new interval would be inserted in the sorted list and check the intervals just before and just after that position.

Why only the neighbors? Because the intervals are non-overlapping and sorted. If the new interval doesn't overlap with its immediate predecessor and doesn't overlap with its immediate successor, then it can't overlap with anything else either. Everything to the left ends even earlier, and everything to the right starts even later.

Algorithm

  1. Maintain a list of (start, end) pairs, sorted by start time.
  2. For each new book(start, end), use binary search to find the index where start would be inserted.
  3. Check the event just before the insertion point (if it exists): does its end time exceed the new start? If prev.end > start, there's an overlap.
  4. Check the event at the insertion point (if it exists): does the new end time exceed its start? If end > next.start, there's an overlap.
  5. If neither overlap exists, insert the new event at the correct position and return true.

Example Walkthrough

1book(10, 20): bookings is empty, no neighbors to check
[]
1/7

Code

The binary search finds neighbors in O(log n), but the array insertion still costs O(n) due to shifting. What if we used a data structure that supports both search and insertion in O(log n)?

Approach 3: Balanced BST (TreeMap / Sorted Set)

Intuition

A balanced binary search tree (like Java's TreeMap, C++'s map, or Python's SortedList) gives us both O(log n) search and O(log n) insertion. This is the natural evolution from Approach 2: keep the same sorted-order neighbor-checking logic but switch to a data structure that doesn't need O(n) shifts.

In a TreeMap, we can use floorEntry to find the closest event starting at or before the new start, and ceilingEntry to find the closest event starting at or after the new start. Check both neighbors for overlap, and if there's no conflict, insert the new event.

Algorithm

  1. Maintain a balanced BST (TreeMap) mapping start times to end times.
  2. For each new book(start, end):
    • Find the floor entry: the event with the largest start time <= start.
    • Find the ceiling entry: the event with the smallest start time >= start.
    • If the floor entry exists and its end time > start, overlap detected.
    • If the ceiling entry exists and end > its start time, overlap detected.
  3. If no overlap, insert (start, end) into the TreeMap and return true.

Example Walkthrough

1book(10, 20): TreeMap empty, no floor/ceiling → insert
[]
1/10

Code