484/670

484. My Calendar I

Medium

Design a calendar that refuses to double-book. Implement a class MyCalendar:

MyCalendar() — creates an empty calendar.
book(start, end) — tries to add an event occupying the half-open interval [start, end): it includes the moment start but not the moment end. If the new event would overlap any previously accepted event, reject it — store nothing and return false. Otherwise save it and return true.

Two events conflict when they share at least one moment in time. Because intervals are half-open, [10, 20) and [15, 25) collide, but [10, 20) and [20, 30) sit back-to-back and are both fine — one event may begin exactly when another ends.

A rejected booking leaves the calendar exactly as it was; only accepted events block future ones.

Example 1 on a timelinebook(15, 25) is rejected because moments 15–19 are already inside [10, 20). book(20, 30) starts exactly at 20, which the first event does not include, so it is accepted.

Example 1:

Input: book(10, 20), book(15, 25), book(20, 30)

Output: [true, false, true]

Explanation: The first event takes [10, 20). The second wants [15, 25), which shares the moments 15 through 19 with the first — rejected. The third wants [20, 30); it starts exactly where the first event ends, and since 20 is excluded from [10, 20), there is no conflict.

Example 2:

Input: book(5, 10), book(10, 15), book(9, 10), book(0, 5)

Output: [true, true, false, true]

Explanation: [5, 10) and [10, 15) are back-to-back, so both are accepted. [9, 10) falls inside the already-booked [5, 10) — rejected. [0, 5) ends exactly where the first event begins, so it fits.

Constraints:

0 ≤ start < end ≤ 10⁹
At most 1000 calls are made to book.

Hints:

Keep every accepted event in a list. Two half-open intervals [s1, e1) and [s2, e2) overlap exactly when s1 < e2 and s2 < e1 — test the new request against each stored event.

Accepted events never overlap, so sorting them by start gives a clean total order. Only two stored events could possibly clash with a new [start, end): the last one starting at or before start, and the first one starting after it.

That neighbor lookup is a floor/ceiling query — bisect on a sorted list in Python, std::map::lower_bound in C++, TreeMap.floorKey/ceilingKey in Java. Accept when the left neighbor ends at or before start and the right neighbor begins at or after end.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: book(10, 20), book(15, 25), book(20, 30)

Expected output: [true, false, true]