Schedule Non-Overlapping Meetings Efficiently
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Implement a meeting scheduler that stores meetings as half-open intervals `[start, end)`, where `start` and `end` are integer timestamps and `start < end`.
The scheduler must support:
1. `book(start, end) -> bool`: Add the meeting if it does not overlap with any existing meeting. Return `true` if the meeting is booked, otherwise return `false` and leave the schedule unchanged.
2. `remove_before(time) -> int`: Given a cutoff timestamp, remove all meetings that end at or before `time`. Return the number of removed meetings.
3. `get_meetings() -> List[Tuple[int, int]]`: Return all currently scheduled meetings sorted by start time.
Follow-up discussion:
- What data structure would you use to optimize `book` and `remove_before`?
- How would the complexity change if you used an unsorted list, a sorted array, or a balanced binary search tree?
- What edge cases should be covered by tests?
Example:
```text
book(10, 20) -> true
book(20, 30) -> true # Adjacent meetings are allowed.
book(15, 25) -> false # Overlaps with [10, 20).
book(5, 10) -> true
remove_before(20) -> 2 # Removes [5, 10) and [10, 20).
get_meetings() -> [(20, 30)]
```
Assume the number of meetings can be large, so the solution should be efficient.
Quick Answer: This question evaluates understanding of interval scheduling and overlap detection, proficiency in selecting efficient data structures for dynamic ordered intervals, and the ability to reason about algorithmic time and space complexity.
You are given a sequence of scheduler operations for meetings stored as half-open intervals [start, end), where start and end are integers and start < end. Adjacent meetings are allowed, so [10, 20) and [20, 30) do not overlap.
Process the operations in order while maintaining the current schedule.
Each operation is one of:
- ("book", start, end): Add the meeting only if it does not overlap any existing meeting. Return True if it was added, otherwise return False.
- ("remove_before", time): Remove every meeting whose end is less than or equal to time. Return the number of removed meetings.
- ("get_meetings",): Return all currently scheduled meetings sorted by start time.
Return a list containing the result of every operation in the same order.
The number of operations can be large, so solutions that scan the full schedule for every booking may be too slow.
Constraints
- 1 <= len(operations) <= 200000
- -10^9 <= timestamp values <= 10^9
- For every book operation, start < end
- get_meetings must return meetings sorted by start time