火车站台数量问题
假设已知某个火车站的所有过往列车的到达arrival和离开departure时间（同一天），如果要求所有列车都不等待直接进站，问至少需要多少个站台。无需考虑晚点等特殊情况。
例如，
Input：
到达时间： arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
离开时间： dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Output：
3 （最多有3辆列车同时进站（在11:00到11:20之间））
解题思路
题目要求找到所有时间中同时在车站的列车的最大数量。一个简单的方案是逐个检查每个车辆的停发时间段，然后看有多少个时间段区间与其有重合，记录最多的重合区间数目，即为待求解的答案。易知，此方法的时间复杂度为O(n^2)。
认真思考后，其实可以有O(nlog_2 n)时间复杂度的方法。思路是将所有的事件 (到达或离开)按时间顺序排序，然后只记录当前还在车站（未离开的）列车。所有时间点中最多数量列车即待求解的答案。
例如，对于上面样例输入，将所有事件按时间排序后得到：
| 时间 | 事件 | 需要的站台数量 |
|---|---|---|
| 9:00 | Arrival | 1 |
| 9:10 | Departure | 0 |
| 9:40 | Arrival | 1 |
| 9:50 | Arrival | 2 |
| 11:00 | Arrival | 3 |
| 11:20 | Departure | 2 |
| 11:30 | Departure | 1 |
| 12:00 | Departure | 0 |
| 15:00 | Arrival | 1 |
| 18:00 | Arrival | 2 |
| 19:00 | Departure | 1 |
| 20:00 | Departure | 0 |
最多需要的站台数量是3，时间段为11:00~11:20
注意，在算法实现时，只需对到达时间arr数组，和离开时间dep数组进行单独排序，然后将两个有序数组再进行归并操作。
网友评论