PPractick

The problem

A station has a timetable of arrivals and departures, as HHMM integers. A train occupies a platform from its arrival until its departure, inclusive: a train arriving at the same minute another departs still needs its own platform. What's the minimum number of platforms so no train waits? That's the maximum number of trains present at any moment. Sort the arrivals and departures separately and sweep through time: each arrival takes a platform, each departure frees one, and an arrival is processed before a departure at the same time.

Example: arrivals [900, 940, 950, 1100, 1500, 1800], departures [910, 1200, 1120, 1130, 1900, 2000] → 3.

Function signature

int findPlatform(vector<int> arr, vector<int> dep);  // dep[i] >= arr[i]

Test cases

Input (arr, dep)	Output	Explanation
([900, 940, 950, 1100, 1500, 1800], [910, 1200, 1120, 1130, 1900, 2000])	3	11:00–11:20 has three trains
([900, 1100, 1235], [1000, 1200, 1240])	1	No overlaps
([1000, 1000, 1000], [1010, 1010, 1010])	3
([900, 905], [905, 910])	2	Arriving as the other leaves still needs a platform
([100], [200])	1

(Confirm: times are within one day; a train occupies its platform during [arrival, departure] inclusive.)

How interviewers phrase it

• "Given arrival and departure times of trains, find the minimum number of platforms required so that no train waits" (GeeksforGeeks "Minimum Platforms").
• It's the same problem as "minimum meeting rooms" (LeetCode 253).

Clarifying questions to ask

1. If a train arrives exactly when another departs, can they share a platform? (Not here: inclusive.)
2. Are times within a single day? (Yes.)
3. Is dep[i] ≥ arr[i] guaranteed? (Yes.)

Follow-ups to expect

1. "Why can the two arrays be sorted independently?"
2. "How do you handle equal times?"
3. "Min-heap alternative?"
4. "Sweep-line alternative?"
5. "Complexity?"

Related questions

• Fractional Knapsack Medium
• N meetings in one room Medium
• Job sequencing Problem Medium
• Shortest Job First Medium
• Insert Interval Medium
• Merge Intervals Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in