The problem
Each booking for one room is a pair (start, end) with start < end. Choose as many bookings as possible so that no two overlap. Return a list of their positions in bookings (counted from 0), in time order: each chosen booking ends no later than the next one starts.
most_bookings([(0, 7), (1, 3), (3, 5), (5, 8), (7, 9), (8, 11)])
# [1, 2, 3, 5]: (1, 3), (3, 5), (5, 8), (8, 11)
Times are half-open, as in Python slices: (s, e) includes s but not e. So a booking that ends at 5 and one that starts at 5 do not overlap.
There can be more than one best choice; any of them is accepted. The tests check how many you chose, and that the choice is allowed (real positions, none twice, in time order, no overlaps). Times are whole numbers and can be below 0.
Limits
- Up to 200,000 bookings. Aim for O(n log n).
Builds on GRDY-3 Interval scheduling.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | No bookings | Not run | |
| 3 | Touching ends | Not run | |
| 4 | One long, many short | Not run | |
| 5 | Short in the middle | Not run | |
| 6 | Copies | Not run | |
| 7 | Nested | Not run | |
| 8 | Negative times | Not run | |
| 9 | 200,000 bookings | Not run |