Implement a BookingCalendar class that accepts bookings as long as they don't overlap any booking already accepted.
BookingCalendar()starts with an empty calendar.book(start, end)tries to reserve the half-open interval[start, end)(sostart < end, and a booking ending at 10 does not clash with one starting at 10). If it doesn't intersect any accepted booking, store it and returnTrue; otherwise leave the calendar unchanged and returnFalse.
cal = BookingCalendar()
cal.book(5, 12) # True
cal.book(10, 14) # False (overlaps [5, 12))
cal.book(12, 20) # True (touches but doesn't overlap)
cal.book(1, 5) # True
cal.book(4, 6) # False
Constraints: 0 <= start < end <= 10**9; the tests make up to 10^5 calls, so scanning every accepted booking on each call is too slow. Aim for O(log n) per call.
Show hint
if the accepted bookings are kept in order of start time, a new booking can only clash with its immediate neighbours in that order.