Minimum Platforms | Optimal Greedy Solution

This classic scheduling problem asks you to find the minimum number of railway platforms required so that no train has to wait. You are given two arrays: arrival times and departure times of trains at a station. The goal is to compute the smallest number of platforms needed so that every arriving train can be accommodated until it departs.

Here’s the [Problem Link] to begin with.

What does the problem say

Given two arrays:

• arr containing arrival times
• dep containing departure times

Find the minimum number of platforms required so that no train waits. A platform occupied by a train from its arrival time until its departure time cannot be used by another train in that interval.

Example 1

arr = [900, 940, 950, 1100, 1500, 1800]
dep = [910, 1200, 1120, 1130, 1900, 2000]
Output: 3
Explanation:
At time around 950 to 1100 multiple trains overlap in the station, so three platforms are needed at peak.

Example 2

arr = [100, 200, 300]
dep = [110, 210, 320]
Output: 1
Explanation:
No overlaps beyond one at any time. One platform is sufficient.

Intuition and Approach (Optimal – Greedy Two-Pointer)

The peak number of trains present at the station at the same time equals the minimum platforms needed. To compute this efficiently:

1. Sort both arrival and departure arrays independently in non-decreasing order.
2. Use two pointers:
   • i points to the next arrival to process.
   • j points to the next departure to process.
3. Maintain a running count of platforms currently needed:
   • If the next arrival time is less than or equal to the next departure time, a new train arrives before the earliest train departs. Increase the count and advance i.
   • Otherwise, the earliest train departs before the next arrival. Decrease the count and advance j.
4. Track the maximum value of the count at any step. That maximum is the answer.

Why this works:

• Sorting allows us to sweep time from earliest events to latest.
• Comparing the next arrival against the next departure tells us whether the number of trains on platforms increases or decreases at that moment.
• The maximum concurrent trains over the sweep is exactly the minimum platforms required.

Code Implementation

Your provided optimal solution, with light comments only and no code changes:

class Solution:
    def minimumPlatform(self, arr, dep):
        arr.sort()
        dep.sort()

        ans = 1
        count = 1
        i = 1
        j = 0
        while i < len(arr) and j < len(dep):
            if arr[i] <= dep[j]:  # one more platform needed
                count += 1
                i += 1
            else:  # one platform can be reduced
                count -= 1
                j += 1
            ans = max(ans, count)
        return ans

Code explanation

• After sorting arrivals and departures, we start with the first train occupying one platform.
• Pointer i scans upcoming arrivals, pointer j scans upcoming departures.
• If the next arrival occurs before or exactly when the earliest pending departure happens, a new platform is needed because a new train has arrived while others are still present.
• If the next departure occurs before the next arrival, a train leaves and frees a platform, so we decrease the current count.
• At each step, update ans with the maximum count observed. This maximum concurrent occupancy equals the required number of platforms.

Note on equality case arr[i] <= dep[j]:

• If a train arrives at the same time another departs, the safe interpretation in this implementation is to require an extra platform momentarily. This matches the conventional problem setting on GFG for counting minimum platforms when an arrival at time t and a departure at time t are treated as overlapping for platform allocation.

Time and Space Complexity

• Precise
  • Sorting arrivals: O(n log n)
  • Sorting departures: O(n log n)
  • Single linear sweep with two pointers: O(n + n)
  • Total time: O(n log n + n + n) which simplifies to O(n log n)
• Simplified
  • O(n log n) time
• Space Complexity
  • Sorting in place plus a few counters and pointers
  • O(1) extra space

Conclusion

The two-pointer greedy sweep after sorting arrivals and departures efficiently finds the peak overlap of trains, which is the minimum number of platforms required. This solution runs in O(n log n) time with O(1) extra space and is optimal for large inputs.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.