Minimum Train Platforms

Problem Given train arrival and departure times at a station, find the minimum number of platforms so that no train waits (equivalently: max number of overlapping intervals at any moment).

Input / Output

• Input: arrays arr[] and dep[] of times (interval i = [arr[i], dep[i]]).
• Output: minimum platform count.

Constraints

• Up to 10^5 trains; O(n log n) expected. Clarify whether arrival exactly at another's departure shares a platform.

Example

• arr = [900, 940, 950, 1100, 1500, 1800], dep = [910, 1200, 1120, 1130, 1900, 2000] → 3.

Expected approach

• Event sweep: sort arrivals and departures separately; two pointers, +1 on arrival, −1 on departure (tie-break per the boundary rule), tracking the running maximum. O(n log n)/O(1). Equivalent: min-heap of active departure times (the meeting-rooms-II formulation). Same skeleton solves merge-intervals and max-concurrent-meetings — recognize the family.