Fewest Platforms for a Station Timetable
Implement fewestPlatforms
A station has a timetable of trains, each with an arrival time and a departure time. A train occupies a platform for its whole stay, including the very moment it departs, so a train that arrives at the exact moment another one leaves still needs a platform of its own. Find the fewest platforms that let every train stop at a platform for its whole stay.
The number of platforms needed equals the largest number of trains in the station at the same moment. Counting the trains present at each arrival works but is quadratic; sorting arrivals and departures separately and sweeping both in time order gets there in O(n log n).
Example 1:
Input: arrivals = [8,12,20,10,25,15], departures = [11,18,24,19,30,17]
Output: 3
Example 2:
Input: arrivals = [1,10], departures = [10,12]
Output: 2
Example 3:
Input: arrivals = [5], departures = [5]
Output: 1
+ 9 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ arrivals.length ≤ 14, and departures.length equals arrivals.length; train i arrives at arrivals[i] and leaves at departures[i] - ●
0 ≤ arrivals[i] ≤ departures[i] ≤ 100 - ●
A train occupies its platform for the whole closed range from its arrival to its departure, inclusive. A train arriving at the exact moment another one departs still needs a different platform - ●
Return the fewest platforms that let every train stop at a platform for its whole stay
arrivals =
departures =