Given the arrival and departure times of trains, find the minimum number of platforms needed. No train should wait.
DSA Animator › DSA Revision › Greedy › Minimum Platforms
Remember: sort the events and sweep the timeline. The answer is the peak number of trains at the same time. The video solves Minimum Platforms (GFG, Medium) with the Sort + Sweep pattern from the Greedy topic, and you can replay every step in the interactive Minimum Platforms animation.
Given the arrival and departure times of trains, find the minimum number of platforms needed. No train should wait.
For six trains arriving at 9 00, 9 40, 9 50, 11 00, 15 00 and 18 00, the answer is 3. Between 11 00 and 11 20, three trains are at the station together.
Checking how many trains overlap each train is O of n squared. We only care about the moments when trains come and go.
Sort the arrival times and the departure times separately. Sweep through time with two pointers, and at each step take whichever event comes first. An arrival adds a platform and a departure frees one, so track the maximum in use.
9 00 arrives, and 9 10 departs, so we are back to 0. 9 40, 9 50 and 11 00 all arrive before the next departure at 11 20. That makes 3 platforms in use, the maximum. Then 11 20, 11 30 and 12 00 depart, and the last two trains need only 2. The answer is 3 platforms.
In code, sort both arrays. While arrivals remain, if the next arrival is not after the next departure, add a platform. Otherwise free a platform, and update the maximum each time. Sorting dominates, so it's O of n log n time.
Remember: sort the events and sweep the timeline. The answer is the peak number of trains at the same time.