Implement a calendar with non-overlapping bookings
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Design a calendar booking system that stores half-open time intervals `[start, end)` (inclusive of `start`, exclusive of `end`).
Implement a class with a method:
- `book(start, end) -> boolean`
The method should:
- Return `true` and add the event if it does **not** overlap with any existing event.
- Return `false` and do **not** add the event if it overlaps with an existing event.
Two events `[s1, e1)` and `[s2, e2)` overlap iff `max(s1, s2) < min(e1, e2)`.
### Example
Operations:
- `book(10, 20)` → `true`
- `book(15, 25)` → `false` (overlaps with `[10,20)`)
- `book(20, 30)` → `true` (touching at 20 is allowed)
### Constraints (typical)
- Up to `10^3` to `10^5` bookings
- `0 <= start < end <= 10^9`
Quick Answer: This question evaluates interval conflict detection and efficient range storage skills, assessing algorithm design and data structure competency within the Coding & Algorithms domain.
Process half-open interval bookings and return whether each booking is accepted.
Constraints
- 0 <= start < end
Examples
Input: ([(10, 20), (15, 25), (20, 30)],)
Expected Output: [True, False, True]
Explanation: Touching at the endpoint is allowed.
Input: ([(5, 10), (1, 5), (10, 15)],)
Expected Output: [True, True, True]
Explanation: Sorted insertion around neighbors.
Input: ([(1, 2), (2, 3), (1, 3)],)
Expected Output: [True, True, False]
Explanation: Later interval can overlap two accepted bookings.
Hints
- Only the predecessor and successor in start-time order can overlap a new interval.