题干

假设已知某个火车站的所有过往列车的到达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}

注：方便起见，输入为int，例如：9:00的输入是900

Output：
3 （最多有3辆列车同时进站（在11:00到11:20之间））

解法1

暴力解法。逐个检查每个车辆的停发时间段，然后看有多少个时间段区间与其有重合，记录最多的重合区间数目，即为待求解的答案。易知，此方法的时间复杂度为O(n^2)。

下面给出代码，代码只经过简单测试，如有误请通过邮箱联系我

from typing import List
from traitlets import Int

class Solution:
    def maxPlatform(self, arr: List[Int], dep: List[Int]) -> Int:
        n = len(arr)
        max_platform = 0
        for i in range(n):
            now_platform = 1
            for j in range(i+1, n):
                if dep[i] > arr[j]:
                    now_platform += 1
                max_platform = max(max_platform, now_platform)
        return max_platform

解法2

将所有的事件 (到达或离开)按时间顺序排序，然后只记录当前还在车站（未离开的）列车。所有时间点中最多数量列车即待求解的答案。该解法的时间复杂度为O(n·logn)

例如上述出发到达时间排序得到下表：

时间	事件	站台数
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站台。

在算法实现时，只需要对arr、dep数组单独排序，然后在进行有序数组的归并排序。下面给出代码：


class Solution {
    public int maxPlatform(int[] arr, int[] dep) {
        int n = arr.length;
        Arrays.sort(arr);
        Arrays.sort(dep); //分别对到达和离开排序
        int numPlatform = 0, maxPlatform = 0;
        int i = 0, j = 0; //两个指针
        while(i < n || j < n) {
            if(i < n && j < n) {
                if(arr[i] < dep[j]) {
                    numPlatform++;
                    i++;
                } else if(arr[i] > dep[j]){
                    numPlatform--;
                    j++;
                } else {
                    i++;
                    j++;
                }
            } else if(j>=n) { // 此时还将继续有火车进站
                numPlatform++;
                i++;
            } else { // 此时只有火车出站
                numPlatform--;
                j++;
            }
            maxPlatform = Math.max(maxPlatform, numPlatform);
//            System.out.println(numPlatform);
        }
        return maxPlatform;
    }
}

总结

这是之前遇到的一道面试题，挺巧妙的。当时没做出来，故做一个小结。

参考资料

火车站台数量问题