If you take the TTC, you'll know that often buses can only carry a certain number of people (call this ).
Sometimes, you get left stranded at the bus stop when the bus is full.
If you're lazy, you'll just wait for the next bus. But sometimes, it might just be better to walk to another stop beforehand.
In our scenario, there is only one bus, and so some people might be required to walk.
Let's suppose you know in advance all of the passengers and where they want to get on and off.
Now, you want to create a plan so that each passenger spends the least amount of time in transit to reach his/her destination.
All passengers are treated equally - we just want to minimize the total time for all passengers.
The bus starts at bus stop and goes "rightward", going to bus stop , then , etc.
The bus stops, numbered , are located along a perfectly straight street.
It takes minutes to walk from one bus stop to the next, and minute to do the same by bus.
Input Specification
Line : Three integers, passengers , stops , capacity .
Next lines: a pair of integers, representing the start and end stops of a passenger.
Passengers get to their starting stops instantly.
Assume that they get to their required bus stop right on time: they won't have to wait for the bus.
All numbers will be positive integers.
Output Specification
The total time taken for all the passengers to get to work, assuming an optimal schedule.
Sample Input 1
3 5 2
1 5
2 5
3 4
Sample Output 1
12
The bus only holds people, so the third guy has to walk. (No passenger is favoured over another)
Passenger : takes the bus ( minutes)
Passenger : takes the bus ( minutes)
Passenger : walks from to ( minutes)
Sample Input 2
5 8 1
1 3
2 4
2 5
6 7
7 8
Sample Output 2
21
In this case, the bus is more like a taxi.
Passenger : Just takes the bus ( minutes)
Passenger : walks to stop first ( minutes) and then takes the bus to ( minute)
Passenger : walks to stop first ( minutes) and then takes the bus to ( minute)
Passengers and : just take the bus ( minutes)
Comments