Minimum Number of Platforms

Count concurrent trains

Sort arrival times and departure times independently. Maintain pointers into both lists and a current platform count. If the next arrival occurs before the next departure, that train needs a platform, so increment the count and advance arrivals. Otherwise release a platform and advance departures. Track the maximum count seen. This is a sweep over event boundaries without needing to match a departure to its original train.

Equality is a requirement detail

Ask whether a train arriving at exactly the same time another departs can use that platform. In the common platform problem, it cannot, so use arrival <= departure to allocate first; in a half-open interval convention use < instead. The comparison is the difference between correct and off-by-one answers. Sorting dominates at O(n log n) time; the scan is O(n), and extra space is O(1) if sorting is in place. Test all overlapping trains, no overlap, identical times, and arrivals or departures near midnight if times are encoded numerically.