Bus Stops

If you take the TTC, you'll know that often buses can only carry a certain number of people (call this C).
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 N 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 #1 and goes "rightward", going to bus stop 2, then 3, etc.
The bus stops, numbered 1,2,3 ... B, are located along a perfectly straight street.
It takes 5 minutes to walk from one bus stop to the next, and 1 minute to do the same by bus.

Input

Three integers, passengers (N) ≤ 1,000,000, stops (B) ≤ 1,000,000, capacity (C) ≤ N
N pairs 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

The total time taken for all the passengers to get to work, assuming an optimal schedule.

Sample Input

3 5 2
1 5
2 5
3 4

Sample Output

12

The bus only holds 2 people, so the third guy has to walk. (No passenger is favored over another)
Passenger 1: takes the bus (4 minutes)
Passenger 2: takes the bus (3 minutes)
Passenger 3: walks from 3-4 (5 minutes)

Sample Input

5 8 1
1 3
2 4
2 5
6 7
7 8

Sample Output

21

In this case, the bus is more like a taxi.
Passenger 1: Just takes the bus (2 minutes)
Passenger 2: walks to stop 3 first (5 minutes) and then takes the bus to 4 (1 minute)
Passenger 3: walks to stop 4 first (10 minutes) and then takes the bus to 5 (1 minute)
Passengers 4/5: just take the bus (1+1 minutes)

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 02, 2008
Author: hansonw1

Problem Types: [Show] [Hide]

• Simulation

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)