Question: 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.
(1st Question form Amazon 3rd F2F)
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. That number is the minimum 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.
PS: If you have a arriving and another departing at same time then put departure time first in sorted array.
Further Thoughts: You 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'.
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Please u explain what is cumulative array???
@Amit:
Cumulative array means an array in which each elements is the cumulative sum of earlier elements is previous array.
Ex:
Parent array = 1 2 3
Cumulative array = 1 3(2+1) 6(3+2+1)
the logic works but how did you come up with this magical logic.Won't the interviewer ask how did you come up with this???
@Surabhi: Thanks! Logic is simple; we have to calculate the maximum number of buses present at bus-station any time.
For this purpose, we have to increment the counter when ever a bus arrives and decrement when a bus leaves. And finally, calculate the maximum value of counter.
@Akash, Thanks for Good Approach, Can You Post Solution for the Same ??
In the Answer section, the first paragraph, it should be min number of platforms not max number of platforms.
Can you please tell me how we can sort time values, thanks