← 返回编程题库
coding-greedy-min-platforms-railway简单免费版2000ms未尝试

铁路时刻表所需的最少站台数

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 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

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。