find the minimum number of platforms so that all the buses can be placed as per their schedule.

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 placed as per their schedule.


Example

Bus         Arrival         Departure 
BusA        0900 hrs        0930 hrs
BusB        0915 hrs        1300 hrs
BusC        1030 hrs        1100 hrs
BusD        1045 hrs        1145 hrs

Algorithm

Its simple dynamic programming question that 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.


I think that code for this will not be complex so I am skipping that part.
The complexity of this solution depends on the complexity of sorting.


Also we don not need to create a cumulative array or an array with 1 and -1;
you just need a counter (cnt) initialized at '0'. Whenever, you find an 'A' in
arrival-departure array, increment cnt by 1. Compare it with maximum value (max);
if it is greater than max, make max equal to cnt. If you get a 'D' in arrival-departure
array, decrement cnt by 1. At the end, return 'max'.

Time Compelxity O(nlogn)

Space Complexity O(1)