Minimum Number of Platforms Required for A Railway Station

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

1. Introduction to Problem

You are given arrival and departure time of trains reaching to a particular station. You need to find minimum number of platforms required to accommodate the trains at any point of time.
For example:

Please note that arrival time is in chronological order.

If you notice we need to find maximum number of trains that can be on the station with the help of arrival and departure time.

2. Using Brute Force Method

You can iterate over all intervals and check how many other intervals are overlapping with it but that will require o(N^2) time complexity.

3. Using Sorting and Comparing Arrival and Departure Array

We will use logic very much similar to merge sort.

  • Sort both arrival(arr) and departure(dep) arrays.
  • Compare current element in arrival and departure array and pick smaller one among both.
  • If element is pick up from arrival array then increment platform_needed.
  • If element is pick up from departure array then decrement platform_needed.
  • While performing above steps, we need track count of maximum value reached for platform_needed.
  • In the end, we will return maximum value reached for platform_needed.
Time complexity : O(NLogN)
Below diagram will make you understand above code better:
When you run above program, you will get below output:

If you are wondering why time complexity is O(NLogN), you should go through merge sort article.

4. Conclusion

In this article, we have discussed the problem of finding the minimum number of platforms required to accommodate the trains at a station. We have seen that a naive brute force approach would take O(N^2) time complexity, where N is the number of trains. We have also presented a more efficient solution that uses sorting and comparing the arrival and departure times of the trains. This solution takes O(NLogN) time complexity.

Was this post helpful?

Leave a Reply

Your email address will not be published. Required fields are marked *