729. My Calendar I — DSA Atlas

729

MediumIntervals and Sweep LineBalanced BST / SortedList of booked half-open intervalsOverlap check on sorted intervals

My Calendar I

Implement MyCalendar with a book(start, end) method for half-open events [start, end). Return True and record the event if it does not double-book (overlap) any existing event; otherwise return False and record nothing.

Open official problem prompt ↗

In plain English

Accept a stream of reservation requests, admitting each only if it does not clash with any previously admitted one.

Picture it like this

A single meeting room with a receptionist. When a request arrives, the receptionist glances only at the booking that ends just before it and the one that starts just after it; if neither collides, the slot is granted.

Example

Input: book(10, 20), book(15, 25), book(20, 30)
Output: [true, false, true]
Why: 10-20 is free; 15-25 overlaps 10-20 so it is rejected; 20-30 only touches 20 (half-open) so it fits.

Constraints

0 <= start < end <= 10^9At most 1000 calls to book

Pattern lesson

See the pattern, then code

Overlap check on sorted intervals

↗

Intervals and Sweep Line

Meetings, schedules, overlapping ranges, resource allocation, or timeline events.. Keep booked intervals sorted by start. A new event [start, end) conflicts only with the interval that would sit just before it (if that one ends after start) or the one just after it (if that one starts before end). A single binary search locates both.

New words, made simpleKnow these before the algorithm

Half-open interval: [start, end) includes start but excludes end, so [10,20) and [20,30) do not overlap
Double booking: Two events sharing any interior instant of time
SortedList: A list kept in sorted order supporting O(log n) bisect and efficient insertion

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Linear scan of all bookings

Fine for the 1000-call limit but does not generalize and wastes the sorted structure.

For each request, compare against every stored interval for overlap.

Time O(n) per booking, O(n^2) totalSpace O(n)

Best choiceSorted intervals with binary search

The idiomatic scalable answer and the pattern interviewers expect.

Keep intervals sorted; a bisect gives the two candidate neighbors to test for overlap.

Time O(log n) query per bookingSpace O(n)

The rule we keep true

Invariant

The stored intervals are always sorted by start and pairwise non-overlapping, so every admitted booking is compatible with all others.

Why this is correct

Reasoning

Because stored intervals never overlap, the new interval's only possible conflicts are with its immediate sorted neighbors. The neighbor at the insertion index is the first interval starting at or after start; it conflicts iff its start is below end. The neighbor before it is the last interval starting before start; it conflicts iff its end exceeds start. Checking these two is both necessary and sufficient.

The algorithm in three movesSay these aloud before coding

1Binary-search the sorted structure for where (start, end) would be inserted

booked = [(10,20)]

2Reject if the next interval begins before the new end

book(15,25): prev end 20 > 15 -> overlap

3Reject if the previous interval ends after the new start

book(20,30): prev end 20 > 20? no -> add

4Otherwise insert the interval and return True

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

[10,20)0

[15,25)1

[20,30)2

1 · Read(10,20)

2 · AskAny neighbor conflict?

3 · Update statesl = []

4 · ResultEmpty -> add -> True

Key takeaway

The second booking clashes with [10,20); the third only touches the boundary and is accepted.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 8Find slot
bisect_left on (start, end) yields the index where the new interval belongs in sorted order.
2
Lines 9-10Right-neighbor check
If the interval at idx begins before end, the two overlap, so reject.
3
Lines 11-12Left-neighbor check
If the interval before idx ends after start, they overlap, so reject.
4
Lines 13-14Commit
No conflict means the booking is safe to insert; return True.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Back-to-back events sharing a boundary like [10,20) and [20,30) must both succeed
Booking fully inside an existing one
Booking fully containing an existing one
First booking on an empty calendar

Common beginner mistakes

Using '<=' / '>=' instead of strict '<' / '>' and wrongly rejecting boundary-touching events
Inserting the interval before the overlap check, corrupting state on a rejected booking
Forgetting the left-neighbor test and only checking the interval at the insertion index

Check your understanding

Why do we test only two neighbors rather than all stored intervals?

PyPython 3 · solution.py

Optimal

1from sortedcontainers import SortedList23class MyCalendar:4    def __init__(self):5        self.sl = SortedList()  # (start, end) tuples67    def book(self, start: int, end: int) -> bool:8        idx = self.sl.bisect_left((start, end))9        if idx < len(self.sl) and self.sl[idx][0] < end:10            return False11        if idx > 0 and self.sl[idx - 1][1] > start:12            return False13        self.sl.add((start, end))14        return True

Time complexityO(log n) search + O(sqrt n) insert per book (O(n) worst case)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAmazonBloomberg

My Calendar I

My Calendar I

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Intervals and Sweep Line