Shared Ride Stop Planner
Lexicographically smallest permutation with interval, order, and capacity limits
A ride-sharing app is planning the stop order for one vehicle. Each rider needs exactly one pickup and one dropoff, and the vehicle starts empty.
Riders are numbered from 0. For rider i, event 2*i is their pickup and event 2*i + 1 is their dropoff. The number of riders is half the length of windows.
The route has exactly len(windows) stop slots, numbered from 0. The pair windows[e] = [earliest, latest] gives the inclusive range of slots in which event e may occur. These are positions in the stop order, not clock times. Every slot must contain exactly one event; waiting slots cannot be inserted.
A valid stop order must satisfy all of the following:
- Every event appears exactly once.
- Every event occurs within its allowed slot range.
- Each rider is picked up before they are dropped off.
- After every event, the number of riders inside the vehicle is at most
capacity.
Return the lexicographically smallest valid list of event IDs. To compare two lists lexicographically, compare their first differing event IDs; the list with the smaller ID comes first.
Return [] if no valid stop order exists. If there are no riders, return [] as the valid empty stop order.
Examples
Example 1
Input: windows = [[0,3],[0,3],[0,3],[0,3]], capacity = 1 Output: [0,1,2,3]
Both riders have unrestricted windows, but the vehicle has only one seat. After the first rider's pickup, that rider must be dropped off before another pickup. Choosing the smallest legal event at each successful branch gives the lexicographically smallest complete order.
Example 2
Input: windows = [[1,2],[2,3],[0,0],[1,3]], capacity = 2 Output: [2,0,1,3]
The window for rider 1's pickup requires it to occupy the first slot. Both riders can be inside the vehicle together, so the remaining events are chosen in lexicographic order subject to their windows and pickup-before-dropoff rules.
Example 3
Input: windows = [[0,0],[1,3],[0,0],[1,3]], capacity = 2 Output: []
Both pickup events must occupy slot 0. Since a slot holds only one event, no valid complete stop order exists.
Constraints
- 0 <= windows.length <= 10
- windows.length is even.
- 1 <= capacity <= 5
- Each windows[e] contains exactly two integers [earliest, latest].
- For every event, 0 <= earliest <= latest < windows.length.
The input need not admit a valid route. The intended solution uses backtracking with incremental constraint checks and deadline pruning. Its worst-case running time is exponential, while its auxiliary space is linear in the number of events, excluding the returned list.
Hints
Show hint 1Hint 1
Build the stop order one event at a time, tracking whether each rider is waiting, onboard, or finished.
Show hint 2Hint 2
Try event IDs in increasing order and stop at the first complete valid order. Abandon a partial order if an unperformed event's latest allowed slot has already passed.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you memoize failed states to support more riders without changing which valid order is returned?
- How would the search change if you needed the number of valid stop orders instead of the lexicographically smallest one?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem