Loading page…
Practice problem · medium
A ride-hailing app lets a driver accept scheduled trips. Each booking is a time window [start, end] in seconds. The driver is busy during the window.
After finishing a booking, the driver wants the next trip that can follow it, with no overlap. For each booking, find the other booking that starts soonest at or after the moment this one ends.
Write next_booking(bookings).
bookings[i] = [start, end], with start < end.i, find the booking j with the smallest start such that start >= end of i. If several have the same smallest start, pick the one with the lowest index.j for each booking i, or -1 when no booking starts at or after the end of i.Input: bookings = [[3, 5], [1, 2], [6, 9], [5, 7], [2, 4]]
Output: [3, 4, -1, -1, 3]Sort the booking indices by start time, then use a binary search on the end of each booking to find the first start that is not before it.
| Booking | End | Starts at or after the end | Next |
|---|---|---|---|
| 0: [3, 5] | 5 | 5 (booking 3), 6 (booking 2) | 3 |
| 1: [1, 2] | 2 | 2 (booking 4), 3, 5, 6 | 4 |
| 2: [6, 9] | 9 | none | -1 |
| 3: [5, 7] | 7 | none | -1 |
| 4: [2, 4] | 4 | 5 (booking 3), 6 | 3 |
Input: bookings = [[1, 2], [2, 3]]
Output: [1, -1]The second booking starts at second 2, exactly when the first ends, so it can follow it.
Input: bookings = [[1, 2], [3, 4], [3, 5]]
Output: [1, -1, -1]Bookings 1 and 2 both start at 3, the earliest start at or after 2. The lower index, 1, wins.
0 ≤ bookings.length ≤ 100,0000 ≤ start < end ≤ 1,000,000,000 (seconds)Scanning all bookings for each booking costs about n × n, which is 10^10 at n = 100,000. Sorting once and then doing a binary search for each booking costs about n log n.
next_booking · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.