Module 13 · Greedy · Greedy Approach

Minimum platforms

Which train leaves doesn't matter, only how many are standing at the station. So turn every arrival and every departure into one event, sort the events by time and walk them like a clock: an arrival takes a platform, a departure frees one. At the same minute the arrivals come first (the sort is stable and they were added first), so a train arriving as another leaves gets its own platform. The most platforms in use at once is the answer.

Each bar is a train on the clock, numbered by its index; the dashed line is the event being handled. trainDetails is the list of events with the pointer i: under each time, A or D (arrival or departure) and the train's number. station shows the trains at a platform.