My Calendar I
Problem statement
You're building a simple scheduler that prevents double-booking a single shared resource — a deploy slot, a shared staging environment, or a maintenance window on a piece of hardware.
An event is a half-open interval [startTime, endTime): every real number
x with startTime <= x < endTime belongs to it, but endTime itself does
not — so an event ending at 20 and one starting at 20 don't actually
overlap.
Implement a MyCalendar class:
MyCalendar()starts with an empty calendar.book(startTime, endTime)adds the event if — and only if — it doesn't share any moment with an event already booked. Returntrueand keep the event if it fits; otherwise returnfalseand leave the calendar unchanged.
Examples
Example 1
Input: ["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output: [null, true, false, true]
Explanation: book(10, 20) books the calendar's first event, so it succeeds. book(15, 25) fails because 15 falls inside [10, 20), which is already booked. book(20, 30) succeeds: the first event covers every moment up to but not including 20, so starting a new event exactly at 20 doesn't share any moment with it.
Hints
[s1, e1) and [s2, e2) overlap exactly when s1 < e2 and s2 < e1 — work through a couple of cases on paper (including two events that touch at one endpoint) to see why both conditions are needed.Approach
Optimal: Binary search on a sorted array
Intuition
Keep events sorted by start time. Once they're sorted, a new booking can only possibly conflict with the event just before where it would be inserted and the event just after — every other event is either entirely earlier or entirely later, and sorting already guarantees that. Binary search finds that exact insertion point in O(log n), so checking those two neighbours is enough; nothing else needs to be looked at.
Steps
- Keep two parallel, sorted-by-start structures: a list of start times and
a list of
(start, end)pairs (both empty at first). - On
book(start, end), binary search the starts list for the indexiwherestartwould be inserted to keep it sorted. - If there's an event just before index
i, check that its end is ≤start— otherwise it overlaps. - If there's an event at index
i(the one that would land right after), check that its start is ≥end— otherwise it overlaps. - If neither check fails, insert
(start, end)at indexiin both lists and returntrue; otherwise returnfalseand leave both lists unchanged.
Dry run
Calls in order: book(10,20), book(15,25), book(20,30).
| call | starts before | insertion index i | before check | after check | result |
|---|---|---|---|---|---|
| book(10,20) | [] | 0 | none | none | true → starts=[10] |
| book(15,25) | [10] | 1 (15>10) | events[0].end=20 > 15 → overlap | — | false |
| book(20,30) | [10] | 1 (20>10) | events[0].end=20 > 20? no, ok | none (i == len) | true → starts=[10,20] |
Result: [true, false, true], matching Example 1.
Edge cases: booking the very first event finds i = 0 with no neighbours on
either side, so it always succeeds. A booking that would land at the very
end of the sorted list only needs the "before" check, since there's no
event after it yet.
Complexity
Time O(log n) - comparisons to find the insertion point and check its two neighbours; inserting into a plain array still costs O(n) in the worst case, since every element after the insertion point has to shift over. So the overall worst-case cost per call is O(n) — the same ceiling as the brute-force scan — but in practice only a handful of comparisons are ever made, instead of up to n.
Space O(n).
from bisect import bisect_left
from typing import List, Tuple
class MyCalendar:
def __init__(self):
self.starts: List[int] = []
self.events: List[Tuple[int, int]] = []
def book(self, start: int, end: int) -> bool:
i = bisect_left(self.starts, start)
if i > 0 and self.events[i - 1][1] > start:
return False
if i < len(self.events) and self.events[i][0] < end:
return False
self.starts.insert(i, start)
self.events.insert(i, (start, end))
return True
if __name__ == "__main__":
cal = MyCalendar()
print(str(cal.book(10, 20)).lower()) # true
print(str(cal.book(15, 25)).lower()) # false
print(str(cal.book(20, 30)).lower()) # trueRecapThe whole problem in a few lines, for the night before
- Spot it: "reject a new booking if it overlaps any existing one" — events are half-open intervals
[start, end) - Idea: two intervals overlap iff
start1 < end2andstart2 < end1; keep bookings sorted and only the two neighbours nearest the new booking's spot can possibly conflict - Cost: brute force O(n) per call; sorted-array binary search does O(log n) comparisons but still O(n) insert; a balanced tree gets both parts to O(log n)
- Trap: using
<=instead of<in the overlap check wrongly rejects back-to-back bookings that only share a boundary point, which the half-open interval explicitly allows
Interview follow-ups
What if a booking should only be rejected once it would cause a *triple* booking, not just a double one (My Calendar III)?
A strict allow/reject overlap check isn't enough anymore — you need to track how many events are active at each point in time. A common approach is a difference array or a balanced map from timestamp to a running "events starting here minus events ending here" delta, so after each booking you can find the maximum number of overlapping events anywhere on the timeline, not just whether one overlap exists.
How would this scale to millions of bookings across many independent calendars?
Give each calendar its own balanced structure (a language's built-in sorted map, or a self-balancing tree) so a single calendar's
bookcalls stay O(log n) even as that calendar grows, and shard calendars across machines by calendar id so no single machine has to hold every calendar's bookings in memory at once.
Frequently asked questions
Because events are half-open, [start, end) — an event ending exactly at 20 and one starting exactly at 20 don't share any moment, since the first event never actually includes 20. Using <= would wrongly reject a booking that starts right where the previous one ends, which is exactly what Example 1's third call does successfully.
You could — an AVL tree or a red-black tree keeps the height at O(log n) no matter what order events arrive in, and that's the real production answer once a calendar has to handle a lot of bookings. It's left out of the "Better" approach here because balancing adds real implementation complexity for a modest win at interview time; the plain BST already shows the core idea of recursing into whichever side can't possibly overlap.
Because a plain array's insert has to shift every element after the insertion point over by one slot, which costs O(n) no matter how fast you found that point. The O(log n) win is in how many comparisons are needed to decide whether the booking is even valid — down from up to n in the brute-force scan to just two — which is usually the part that matters in an interview. A language's balanced tree or sorted set (Java's TreeMap, C++'s std::map, Python's sortedcontainers.SortedList) gets both the search and the insert down to O(log n).
Reserving an exclusive time slot on a single shared resource — a deploy pipeline, a shared staging environment, a maintenance window on a piece of hardware — without double-booking it is exactly this problem, just with different labels on the two ends of each interval.