Journey planning

Question

If you have the full bus schedule for a country, how can you find out the maximum number of people that can be carried between between two specified stops in 1 day?

I assume a bus schedule gives you the full list of leaving and arriving times for every bus stop and also the capacity of each bus. You are given the start and end stop in the question.

You could determine a sequence of buses that gives the shortest time to the destination and fill up all the buses that leave from the start going along this path and then when each bus arrives at a stop, just transfer as many passengers as possible to the next bus that is leaving. There is no reason why this should have maximal capacity however.

What is the fastest this problem can be solved? For example, suppose that for M cities I'm given a total of N records; route record Rᵢ contains a number Kᵢ, a capacity Cᵢ, and lists of Kᵢ city numbers, Kᵢ arrival times, and Kᵢ departure times. (The first arrival time and the last departure time in Rᵢ are irrelevant.) Can a breadth-first search program solve the question in O(M*N) time?

Answer 1

This isn't a weird puzzle; it's an algorithms question. One way to solve this is to make a directed graph with a node for every (location, arrival time) and (location, departure time). Each arrival node has an infinite capacity arc to all departures at the same location that aren't earlier. Each departure node has an arc to each of the appropriate arrival nodes (per the bus schedule), weighted with the capacity of the bus. Then you can use your favorite algorithm to find the maximum flow from your source to your sink.

Your source node should be an arrival node at time zero at your start location, your sink node should be a departure node at the ending time at your ending location.