Minimum Platforms
A station has one day's timetable: train i arrives at arrival[i] and leaves at departure[i]. Times are HHMM numbers, the clock time without its colon, so 930 is 09:30.
A train holds its platform from the minute it arrives through the minute it leaves, both included. So a train arriving in the minute another leaves cannot take that train's platform.
Return the fewest platforms the station needs so that no train has to wait.
Function
- arrivalinteger-array
- the arrival time of each train, as an HHMM number
- departureinteger-array
- the departure time of each train, as an HHMM number; departure[i] belongs to arrival[i]
- Returnsinteger
- the largest number of trains at the station in the same minute, which is the fewest platforms needed
Constraints
1 ≤ arrival.length == departure.length ≤ 50000 ≤ arrival[i] ≤ departure[i] ≤ 2359- Every time is a valid
HHMMtime: its last two digits are at most 59. - All trains run on the same day. The arrays are not sorted.
Examples
- Input
- arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
- Output
- 3
- Explanation
- At 15:30 three trains stand at the station: the ones from 15:00 to 16:00, from 15:20 to 15:35 and from 15:30 to 15:45. No minute has four, so
3platforms are enough.
- Input
- arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
- Output
- 2
- Explanation
- The train arriving at 12:30 meets the one leaving at 12:30, and the same happens at 13:00. Each of those minutes has two trains at the station, so the answer is
2, not 1.
- Input
- arrival = [600, 700, 1300]departure = [2200, 715, 1400]
- Output
- 2
- Explanation
- The train from 06:00 to 22:00 keeps one platform busy all day. The trains from 07:00 to 07:15 and from 13:00 to 14:00 never meet, so they share a second platform:
2.
Follow-up
Some night trains arrive before midnight and leave after it, so their departure number is smaller than their arrival. How would you count platforms when the timetable wraps around midnight?
Hints
Open them one at a time. Each one gives away a little more.
Forget which train uses which platform for a moment. Pick any one minute of the day: how many platforms does that minute alone force you to have?
The number of trains at the station only rises when a train arrives and only falls when one leaves. Go through those events in time order with a running count, and the largest count is the answer. On a tie the arrival comes first, because the leaving train still holds its platform in that minute.
Sort the arrival times and the departure times as two separate lists, with one pointer in each. If the next arrival is at or before the next departure, add a train and record the peak; otherwise remove a train. Stop when the arrivals run out.
Solution
The answer is the largest number of trains at the station in the same minute. The work is finding that busiest minute without comparing every pair of trains. Sort arrivals and departures separately, and one walk through the day's events with a running count finds it in O(n log n).
Count the trains at each arrival
Correct, but does not finish on the largest tests
Intuition
Trains standing in the same minute all need different platforms, so the busiest minute is a lower bound. It is also enough: open a new platform only when an arriving train finds every open one occupied. At that minute a train stands on each open platform plus the new one, so you never open more than the peak.
The count of trains present only rises when a train arrives, so the busiest minute is some train's arrival minute. For each train i, count the trains j with arrival[j] ≤ arrival[i] ≤ departure[j]. Both comparisons use ≤ because a train still stands on its platform in the minute it leaves.
Each of the n trains checks all n, so the work is O(n²): 25 million pair checks for 5000 trains.
Algorithm
- Set
most = 0. - For each train
i, count the trainsjwitharrival[j] ≤ arrival[i] ≤ departure[j]. - If that count is larger than
most, store it. - Return
most.
def minimumPlatforms(arrival, departure):
n = len(arrival)
most = 0
for i in range(n):
# trains standing at the station in the minute train i arrives
here = 0
for j in range(n):
if arrival[j] <= arrival[i] <= departure[j]:
here += 1
most = max(most, here)
return mostSort both lists and sweep with two pointers
Intuition
The number of trains present depends only on how many have arrived and how many have left by a given minute, not on which train leaves when. So sort the arrival times and the departure times as two independent lists. Read together in time order, they are the day's events: an arrival adds a train, a departure removes one.
On a tie the arrival goes first, because the leaving train still holds its platform in that minute. In the first example the count is back to 0 after departure 1100, then arrivals 1500, 1520 and 1530 all come before departure 1535, so it reaches 3.
Once the arrivals run out, the remaining departures can only lower the count, so the walk stops there. Sorting costs O(n log n) and the walk takes at most 2n steps.
Algorithm
- Sort a copy of
arrivaland a copy ofdeparture. - Set
platforms,most,iandjto0. - While
i < n: ifarrivals[i] ≤ departures[j], add 1 toplatforms, updatemostand moveion. - Otherwise subtract 1 from
platformsand movejon. - Return
most.
def minimumPlatforms(arrival, departure):
arrivals = sorted(arrival)
departures = sorted(departure)
n = len(arrivals)
platforms = 0 # trains at the station right now
most = 0
i = 0 # next arrival
j = 0 # next departure
while i < n:
if arrivals[i] <= departures[j]:
# the next event is an arrival; on a tie the leaving train is still there
platforms += 1
most = max(most, platforms)
i += 1
else:
platforms -= 1
j += 1
return most
Pitfalls and edge cases
- Comparing with
<where the inclusive rule needs≤. In the second example each arriving train then takes the platform of the train leaving that minute, and the answer drops from 2 to 1. - Subtracting
HHMMnumbers: 1300 minus 1259 is 41, though the times are one minute apart. Comparing them is safe, and the solution only compares. - Sorting the trains by arrival and comparing each one only with the train before it. A long stay like 06:00 to 22:00 in the third example overlaps trains far down the list.
- Skipping trains that arrive and leave in the same minute. Four trains that each stand from 10:00 to 10:00 need four platforms.
Frequently asked questions3
What is the time complexity of the minimum platforms problem?
Sorting the two arrays costs O(n log n) and the sweep after it O(n), so the sorts dominate. The sorted copies take O(n) extra space.
How is minimum platforms different from meeting rooms II?
Both ask for the most intervals that overlap at one moment. Here a train holds its platform through the minute it leaves; in meeting rooms II a room is free the moment its meeting ends. In the sweep that is one comparison: on a tie you process the arrival first here, and the ending meeting first there.
Can minimum platforms be solved without sorting?
Yes, since every time fits a fixed clock. Index 2401 counters by the HHMM number, add 1 at each arrival and subtract 1 at departure + 1. The largest running sum is the answer: O(n + 2400) time. Indexes such as 1260 to 1299 are not clock times and get no arrival, so they never set a peak.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def minimumPlatforms(arrival, departure):
# Write code hereTest #1
Test #2
Test #3
Arguments
arrival = [900, 1500, 920, 1520, 1000, 1530] departure = [930, 1600, 1010, 1535, 1100, 1545]
Expected Output
3