## Saturday, March 19, 2011

### Bus Station Puzzle -A DP Approach

At a bus-station, you have time-table for buses arrival and departure. You need to find the minimum number of platforms so that all the buses can be accommodated as per their schedule.

Example: Time table is like below:

Bus

Arrival

Departure

BusA

0900 hrs

0930 hrs

BusB

0915 hrs

1300 hrs

BusC

1030 hrs

1100 hrs

BusD

1045 hrs

1145 hrs

Then the answer must be 3. Otherwise the bus-station will not be able to accommodate all the buses.

Answer:

Let’s take the same example as described above. Now if we apply dynamic programming and calculate the number of buses at station at any time (when a bus comes or leaves). Maximum number in that pool will be nothing but the maximum number of buses at the bus-station at any time, which is same as max number of platforms required.

So first sort all the arrival(A) and departure(D) time in an int array. Please save the corresponding arrival or departure in the array also. Either you can use a particular bit for this purpose or make a structure. After sorting our array will look like this:

0900

0915

1930

1030

1045

1100

1145

1300

A

A

D

A

A

D

D

D

Now modify the array as put 1 where you see A and -1 where you see D. So new array will be like this:

1

1

-1

1

1

-1

-1

-1

And finally make a cumulative array out of this:

1

2

1

2

3

2

1

0

Your solution will be the maximum value in this array. Here it is 3.

The complexity of this solution depends on the complexity of sorting.

Soln Provided By Aakash