My Calendar I — Book Events Without Double Booking

Problem Statement

Implement a MyCalendar class to store events without causing a double booking.

A double booking happens when two events overlap (share at least one common time instant).

Implement:

• book(start, end) — Returns true if the event [start, end) can be added without overlapping an existing event, and adds it. Otherwise returns false and does not add it.

Note: [start, end) is a half-open interval — an event ending at time t and another starting at t do NOT overlap.

Constraints

• 0 <= start < end <= 10^9
• At most 1000 calls to book
• Aim for better than O(n) per booking if possible

Example

MyCalendar cal = new MyCalendar();
cal.book(10, 20);  // returns true
cal.book(15, 25);  // returns false (overlaps [10,20))
cal.book(20, 30);  // returns true (starts exactly when [10,20) ends)

What the Interviewer Expects

1. Naive approach — store all booked intervals in a list, check each new booking against all (O(n) per booking).
2. Optimal: balanced BST / TreeMap — store intervals sorted by start. For a new [start, end), use floor and ceiling to find the nearest intervals and check only those. O(log n) per booking.
3. Overlap condition — two intervals [s1,e1) and [s2,e2) overlap iff s1 < e2 && s2 < e1.
4. Production-ready code — clean interval handling, correct half-open interval logic.

Follow-ups

1. My Calendar II — allow double bookings but not triple. How does the approach change?
2. My Calendar III — return the max number of concurrent events at any time (sweep line).
3. What if you also need to cancel a booking?
4. What data structure gives O(log n) for both insert and overlap check?