My Calendar I

Problem

Implement a booking calendar that refuses overlapping events. Each event is a half-open interval [start, end). Two events conflict if they share any instant; an event ending at time t and another starting at t do not conflict.

Design the class MyCalendar:

• MyCalendar() creates an empty calendar.

• book(start, end) -> bool adds the event if it does not conflict with any previously accepted event and returns True; otherwise it leaves the calendar unchanged and returns False.

• Start and end times are non-negative and fit comfortably in a normal int, with start < end.

• No more than about a thousand calls to book.

Examples

• book(12,25) → True, book(18,30) → False, book(25,40) → True. The second overlaps [12,25); the third starts exactly when the first ends, which is allowed.
• book(5,10) → True, book(0,5) → True, book(4,6) → False. Bookings can be added out of order; [4,6) clashes with both neighbors.
• book(1,2) → True, book(1,2) → False. Re-booking the same slot fails.

Hints

1. To decide whether [start, end) conflicts with an existing event [s, e), what single condition must hold?
2. If accepted events were kept sorted by start, which events could possibly conflict with a new one?
3. Keep the events in a sorted list; binary-search the insertion point and check only the predecessor and successor.