Katkat
Back

Schedule Non-Overlapping Meetings Efficiently

UberSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manage dynamic intervals and determine if a new meeting can be scheduled without overlapping existing appointments using efficient data structures.

Problem Statement

You are building a meeting scheduling system. You need to design a class MeetingScheduler that maintains a set of non-overlapping meetings. A meeting is defined by a start time and an end time [start, end), where the interval is inclusive of the start time and exclusive of the end time.

Implement the following methods:

  1. book(start, end): Attempts to book a meeting from start to end. If the new meeting does not overlap with any existing meetings, add it and return true. Otherwise, do not add it and return false.
  2. get_all_meetings(): Returns a list of all currently booked meetings, sorted by start time.

Constraints

  • 0 <= start < end <= 10^9
  • The number of calls to book will not exceed 10^5.

Examples

# Example 1
scheduler = MeetingScheduler()
scheduler.book(10, 20) # returns True
scheduler.book(15, 25) # returns False (overlaps with 10-20)
scheduler.book(20, 30) # returns True
scheduler.get_all_meetings() # returns [[10, 20], [20, 30]]

Edge Cases

  • Booking a meeting that starts exactly when another ends (e.g., [10, 20] and [20, 30]) should be allowed.
  • Handling empty schedules.
  • Extremely large time ranges.

Hints

Hint 1

Consider maintaining the meetings in a sorted list or an ordered data structure to allow for binary search.

Hint 2

For a new interval [start, end), you need to check if there is an existing meeting that starts before the new end and ends after the new start.

Hint 3

Using a balanced binary search tree or a sorted list with binary search insertion can help you find potential overlaps in O(log N) time.

Follow-up questions

  • How would you modify your implementation to support a `cancel(start, end)` method?
  • What would change if you were allowed to book overlapping meetings, but needed to return the maximum number of concurrent meetings occurring at any point in time?
  • If the number of meetings is massive and queries are frequent, how could you optimize the space complexity?