Minimum Number of Platforms for a Bus Station You are given a | Cse interview questions

Minimum Number of Platforms for a Bus Station

You are given a data of n buses that reach a bus station. Two arrays represent arrival and departure times of buses that stop at the station.

You need to find the minimum number of stations so that none of the buses overlap.

Examples :

Input 1 :
arr = [8:00, 5:10, 12:40, 12:00, 12:15, 20:08]
dep = [8:10, 5:30, 12:55, 12:45, 12:50, 20:32]

Output 1 :
3

Explanation 1 :

The buses which arrive at 8:00, 5:10 and 20:08 do not overlap with any other buses as till their departure time, no other buses have arrived.

For the buses which arrive at 12:00, 12:15, 12:40, all the three buses stay at bus station during the interval 12:40 to 12:45 hours as their departure time has not yet arrived during this time interval.

So atleast 3 platforms are needed for the bus station.

(Note that here arr and dep array variable denotes the arrival and departure times of the buses.)

Input 2 :
arr = [18:40, 17:05, 14:12]
dep = [18:50, 17:25, 14:42]

Output 2 :
1

Explanation 2 :

Here we can see that the arrival and departure timings of three buses do not overlap. So minimum number of station needed is 1.

Topic : Greedy Algorithm

Reference(s) ->
GeeksforGeeks

Solution ->
GFG Article Set 1, Set 2

Asked in Amazon

Join our Official Channel @cseinterview