Minimum Platforms Required For a Railway Station | Coding Interview | Sorting

Minimum Platforms needed!

This is an easy-medium category problem and has been asked several times by Amazon, Airtel, Hike and Paytm.

After reading each section, to get more benefit out of this article, try to code each approach yourself, even the brute force. I have provided the properly commented code with an explanation for your reference.

Part of the 30 days preparation plan.

Table of Contents

• Description
• Brute Force Approach
• Efficient Solution using Sorting
• Code
• Time and Space Complexity

Description

For a Railway Station, We are given arrival and departure timings of N trains in two arrays, let's call them Arrival and Departure.

We have to find the minimum number of platforms needed so that no train needs to wait for the railway station to have an empty platform.

Example 1:
Arrival:   [9.00, 10.00, 9.40,  14.10, 15.30]
Departure: [9.50, 14.00, 10.10, 14.20, 17.30]
Output: 2
Explanation: 3rd Train's timing intersects with 2nd Train's schedule (10.00 to 14.00). Hence we need at least 2…