All problems

Train Platforms

Medium · heap

A station has as many platforms as it needs, numbered 1, 2, 3, .... You are given a list trains, where each item [arrive, depart] is one train that stands at a platform from time arrive until time depart. Always arrive < depart.

The trains are handled in order of arrival. If two trains arrive at the same time, the one that appears earlier in trains is handled first. When a train arrives it takes the lowest-numbered platform that is free at that moment. A platform is free if it has never been used, or if the train on it departs at or before the new arrival time. So a train that departs at time t leaves its platform free for a train arriving at t.

Return a list with the platform number used by each train, in the same order as the input trains.

Examples

Example 1

Input: trains = [[1, 4], [2, 5], [4, 6]]

Output: [1, 2, 1]

The first two trains overlap, so they take platforms 1 and 2. The third arrives at 4, exactly when platform 1 empties, so it takes platform 1.

Example 2

Input: trains = [[5, 9], [1, 3], [2, 6], [3, 8]]

Output: [3, 1, 2, 1]

By arrival time the order is [1, 3], [2, 6], [3, 8], [5, 9]. They take platforms 1, 2, 1 (free again at 3) and 3 (platforms 1 and 2 are both busy at 5). The answer is listed in input order.

Example 3

Input: trains = [[1, 2], [1, 2], [1, 2]]

Output: [1, 2, 3]

All three arrive together, so the earlier one in the list gets the lower platform.

Constraints