铁路时刻表所需的最少站台数
Minimum Platforms for a Railway Schedule
开始编码某个小型铁路站的调度台正在编排明天的时刻表,需要测算最少需要几个站台才能让所有列车互不冲突地停靠。给定两个等长列表:arrivals[i] 和 departures[i] 分别是第 i 列车的到达时刻和出发时刻(整数分钟或任何统一时间单位)。一个站台同一时间只能停一列车——列车到达后会连续占用站台直到出发;某列车一旦离开,腾出的站台就可以被后续(或同一时刻)到达的列车复用,但前提是前一列车必须已经离站。两列车若到达和出发的时刻完全相同,它们的占用窗口是闭区间——边界上仍重叠——必须分别占两个站台。请计算够用的最少站台数。
请实现 solution(arrivals: list[int], departures: list[int]) -> int,返回站内同时停靠列车数的峰值——等价地,N 条闭区间 [arrivals[i], departures[i]] 的最大重叠数。
示例:solution([900], [1000]) → 1(一列车一站台)。solution([1, 2, 3], [10, 11, 12]) → 3(三列车在 [3, 10] 整段都重叠,需 3 个站台)。solution([900, 940, 950, 1100, 1500, 1800], [910, 1200, 1120, 1130, 1900, 2000]) → 3(六列车经典例子:在 [1100, 1120] 期间三列车同时在站,峰值 3)。
算法:把两个数组各自独立排序(关键技巧——配对关系对「同时占用几个」无影响,只关心时刻多重集);然后用双指针扫合并后的时间轴,每个到达让 cur += 1 并刷新峰值,每个出发让 cur -= 1,峰值就是答案。总开销是排序的 O(N log N) 加扫描的 O(N)。
实务背景:这是「峰值并发容量」最经典的套路,几乎所有资源调度系统都会复用:办公楼一天的会议预订需要几间会议室;急诊一段时间的就诊潮需要几张床;某个服务在峰值负载下需要几条数据库连接;高频交易团队的策略集群在 colo 机房里需要几个机架才能不排队。算法都一样——独立排序后扫一遍——因为本质就是在算「并发占用函数」在时间上的 L∞ 范数。
约束条件
- 0 ≤ N ≤ 10⁴,其中 N = len(arrivals) = len(departures)
- len(arrivals) == len(departures);第 i 列车的占用区间是 `[arrivals[i], departures[i]]`
- 0 ≤ arrivals[i] ≤ departures[i](允许到达与出发为同一时刻——仍需占用一个站台)
- 区间两端都**闭合**:如果一列车到达的瞬间正好另一列车离开,它们仍各占一个站台
- 空输入(`N == 0`)返回 `0`
样例
Case 1 · empty schedule
输入: [[],[]]
期望: 0
没有列车,自然不需要任何站台,返回 0。
Case 2 · single train
输入: [[900],[1000]]
期望: 1
只有一列车,一个站台就够了。
Case 3 · classic six-train schedule
输入: [[900,940,950,1100,1500,1800],[910,1200,1120,1130,1900,2000]]
期望: 3
把到达和出发分别排序后做扫描线:到达指针推进时占用 +1,出发指针推进时占用 -1。在 1100 时刻三列车(940→1200, 950→1120, 1100→1130)同时在站,峰值为 3。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · empty schedule
输入: [[],[]]
期望: 0
没有列车,自然不需要任何站台,返回 0。
Case 2 · single train
输入: [[900],[1000]]
期望: 1
只有一列车,一个站台就够了。
Case 3 · classic six-train schedule
输入: [[900,940,950,1100,1500,1800],[910,1200,1120,1130,1900,2000]]
期望: 3
把到达和出发分别排序后做扫描线:到达指针推进时占用 +1,出发指针推进时占用 -1。在 1100 时刻三列车(940→1200, 950→1120, 1100→1130)同时在站,峰值为 3。