Design a meeting scheduler API

Meeting Scheduler (OOD + data structures)

Design and implement an in-memory meeting scheduler that stores existing bookings and can answer availability queries.

You must support two operations:

1. addBooking(start, duration)
   • Adds a booking covering the time interval [start, start + duration) .
   • Assume start is an integer timestamp (e.g., minutes) and duration > 0 .
2. earliestStart(requestStart, duration)
   • Given a desired start time and meeting duration, return the earliest time t >= requestStart such that the interval [t, t + duration) does not overlap any existing booking.

Overlap definition

Two bookings overlap if their half-open intervals intersect. For example, [10, 20) and [20, 30) do not overlap.

Follow-ups

• Can you make earliestStart run in O(N) time (where N is the number of bookings) by changing how you store data?
• Can you support faster than O(N) (e.g., O(log N) insert/query) with a better data structure?
• Make the scheduler thread-safe . Assume the workload is write-heavy .

State any assumptions you need (e.g., whether addBooking is guaranteed not to conflict, or whether conflicts should be rejected/merged).