Calendar Booking Scheduler
Google● MediumFULLTIMEONSITE INTERVIEWProblem statement
Implement a calendar scheduler that processes booking attempts in their given order. The i-th attempt requests the half-open time interval [starts[i], ends[i]). Accept an attempt if it has no positive-length overlap with any previously accepted booking. Otherwise reject it; a rejected attempt does not occupy time.
Return a boolean array whose i-th value says whether that attempt was accepted. Intervals that meet at an endpoint do not overlap. For example, [10, 20) and [20, 30) can both be booked.
Function
scheduleBookings(starts: int[], ends: int[]) → boolean[]Examples
Example 1
starts = [10,15,20]ends = [20,25,30]return = [true,false,true]The first booking occupies [10, 20). The second overlaps it, while the third touches its endpoint and is accepted.
Example 2
starts = [5,5,6,0]ends = [6,10,8,5]return = [true,false,true,true]The rejected [5, 10) attempt does not block [6, 8). The final [0, 5) attempt touches the first booking without overlap.
Example 3
starts = [10,12,14]ends = [20,18,16]return = [true,false,false]Both later attempts are contained inside the first accepted booking, so each is rejected.
Constraints
1 <= starts.length <= 2000.ends.length == starts.length.0 <= starts[i] < ends[i] <= 10^9.- Process attempts in array order, retaining only accepted bookings.