My Calendar I
Problem
MyCalendar whose book(start, end) tries to
reserve the half-open interval [start, end). If it overlaps any event already
accepted, reject it and return false; otherwise store it and return
true. Touching intervals (one ends exactly when the next starts) are fine.book(10,20) book(15,25)Outputtrue, falsebook(20,30)Outputtrue0 ≤ start < end ≤ 109 · at most 1000 calls to book
Try it yourself
class MyCalendar {
public boolean book(int start, int end) {
}
}
[s1,e1) and [s2,e2) overlap iff
s1 < e2 && s2 < e1. Accepted events never overlap, so if they are kept
sorted by start, a new event only has to be checked against its two neighbours.Instinct Keys keep arriving or leaving and you must ask "what is the nearest key below/above x?" or "current min/max" each time - reach for TreeMap/TreeSet.
Memory hack A HashMap with a sense of direction - floor looks down, ceiling looks up, and both answer in log time while the data keeps changing.
Open the Ordered Set (TreeMap) guide →Approaches
Brute ForceList of Events, Linear Scan
O(n) per bookSpace O(n)Keep every accepted interval in a list. For a new request, test the overlap condition against all of them; append it only if none conflicts.
class MyCalendar { private final List<int[]> events = new ArrayList<>(); public boolean book(int start, int end) { for (int[] e : events) { if (e[0] < end && start < e[1]) return false; // overlap } events.add(new int[]{start, end}); return true; } }
Trivial and fine for 1000 calls, but each booking scans everything.
BetterHand-Rolled BST of Intervals
O(h) per bookSpace O(n)Store events in a binary search tree ordered by time. A new event goes
left if it ends before the node starts, right if it starts after the
node ends, and otherwise it overlaps — reject. Average
h = O(log n), but sorted inputs degrade to a chain (O(n)).
class MyCalendar { private class Node { int start, end; Node left, right; Node(int s, int e) { start = s; end = e; } } private Node root; public boolean book(int start, int end) { if (root == null) { root = new Node(start, end); return true; } Node cur = root; while (true) { if (end <= cur.start) { if (cur.left == null) { cur.left = new Node(start, end); return true; } cur = cur.left; } else if (start >= cur.end) { if (cur.right == null) { cur.right = new Node(start, end); return true; } cur = cur.right; } else { return false; // overlaps cur } } } }
Fast on random input, but unbalanced — worst case is still linear.
OptimalTreeMap Floor / Ceiling Neighbours
O(log n) per bookSpace O(n)A TreeMap<start, end> is a self-balancing BST. Only two
events can clash: the one starting at or before start
(floorEntry) must end by start, and the one starting at
or after it (ceilingKey) must start no earlier than
end.
class MyCalendar { private final TreeMap<Integer, Integer> calendar = new TreeMap<>(); public boolean book(int start, int end) { Map.Entry<Integer, Integer> prev = calendar.floorEntry(start); Integer next = calendar.ceilingKey(start); if (prev != null && prev.getValue() > start) return false; // prev runs into us if (next != null && next < end) return false; // we run into next calendar.put(start, end); return true; } }
Guaranteed O(log n) per call with library code — the expected answer.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | List of Events, Linear Scan | O(n) per book | O(n) |
| Better | Hand-Rolled BST of Intervals | O(h) per book | O(n) |
| Optimal | TreeMap Floor / Ceiling Neighbours | O(log n) per book | O(n) |
- Using
≤in the overlap test — rejects valid touching intervals like [10,20) and [20,30). - Checking only the floor neighbour and forgetting the ceiling one (or vice versa).
- Storing a rejected booking anyway — later checks become wrong.
- Write the overlap condition first and test it on touching / nested intervals.
- Ask about call volume: 1000 calls makes O(n) fine, but mention the O(log n) upgrade.
- Explain why a plain BST can degrade and how TreeMap (red-black tree) avoids it.