Design & Implement a Booking Scheduler (Earliest Available Start)

Coding / Design: Implement a Booking Scheduler Implement a Scheduler that stores non-overlapping bookings on a timeline and, given a requested time window, returns the earliest feasible start time. Time model All times are integers (e.g., minutes). A booking is a half-open interval [start, end) where end = start + duration. Bookings must not overlap (adjacent is allowed). APIs add_booking(start: int, duration: int) -> None Add [start, start + duration) into occupied bookings. Inputs are guaranteed not to overlap existing bookings. earliest_start(request_start: int, duration: int) -> int Return the smallest integer t >= request_start such that [t, t+duration) does not overlap any existing booking. Constraints Number of bookings N up to 2 * 10^5. Time values up to 10^9. Explain and implement the time complexity of core operations. I/O for this implementation Read from stdin: First line: integer Q. Next Q lines: ADD start duration QUERY request_start duration Print one line per QUERY: the earliest feasible start time. Example Input 6 ADD 10 5 ADD 20 5 QUERY 0 5 QUERY 12 5 QUERY 15 5 QUERY 20 1 Output 0 25 15 25