Bus Depot Inspection Runs
Indices of minimum-cost subsets covering every element exactly once
A city bus depot must inspect every stop in its network overnight. Stops are numbered from 0 through stops - 1.
The depot has several preset inspection runs. routes[i] lists the stops inspected by run i, and fares[i] is the cost of dispatching that run. Every listed stop is inspected when its run is dispatched; a run cannot be shortened.
Choose a subset of runs so that each stop is inspected exactly once. Thus, selected runs must not share any listed stop, and together they must include every stop.
Among valid plans, choose one using these priorities, in order:
- Smallest total dispatch cost.
- Fewest selected runs.
- Lexicographically smallest list of selected run indices, after sorting the indices in increasing order.
Return that increasing list of run indices. If no valid plan exists, return [-1].
Two runs may list the same set of stops; they are still separate choices with their own indices and costs. The order of stops within a run does not affect the plan.
Examples
Example 1
Input: stops = 4, routes = [[0,1],[2,3],[0,2],[1,3],[0,1,2,3]], fares = [4,4,3,5,8] Output: [4]
Several plans have the same total cost, but the single run inspecting all four stops wins the fewest-runs tie-break.
Example 2
Input: stops = 3, routes = [[0,1],[2],[0],[1,2]], fares = [4,2,2,4] Output: [0,1]
There are two equally priced two-run plans. Their sorted index lists are compared lexicographically to determine the selected plan.
Example 3
Input: stops = 3, routes = [[0,1],[1,2]], fares = [1,1] Output: [-1]
Both available runs inspect stop 1. Taking both would inspect that stop twice, while taking only one leaves another stop uninspected, so no valid plan exists.
Constraints
- 1 <= stops <= 18
- 0 <= routes.length <= 50
- fares.length == routes.length
- 1 <= routes[i].length <= stops
- Each routes[i] contains distinct integers in the range [0, stops - 1].
- 0 <= fares[i] <= 1000000
The intended solution is exponential memoized backtracking, not greedy route selection. With n stops and m runs, it uses O(2^n * m * n) time and O(2^n * n + m * n) space in the worst case, including stored canonical index lists. Adding the same run to equal-length completion lists preserves their lexicographic order, which makes the specified tie-breaking compatible with memoization.
Hints
Show hint 1Hint 1
At any partial plan, choose an uncovered stop. Every completion must select exactly one currently compatible run containing that stop. Choosing the stop with the fewest compatible runs reduces branching.
Show hint 2Hint 2
Represent covered stops with a bitmask. The best completion depends only on this mask, so cache it together with its cost, run count, and canonical sorted index list.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also count the number of plans achieving both the minimum cost and the minimum number of runs?
- How could you safely preprocess runs that inspect identical stop sets while preserving all three tie-breaking rules?
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