Minimum Platforms
车站有一天的时刻表：列车 i 在 arrival[i] 时刻到达，并在 departure[i] 时刻离开。时间用 HHMM 数字表示，也就是省略冒号的钟表时间，所以 930 表示 09:30。
列车从到达的那一分钟起，一直到离开的那一分钟（包括这两分钟）都占用站台。因此，一列车到达时，如果另一列车正好在这一分钟离开，它就不能使用那列车的站台。
返回车站所需的最少站台数，确保没有列车需要等待。
函数
- arrivalinteger-array
- 每列火车的到达时间，以 HHMM 数字表示
- departureinteger-array
- 每趟列车的出发时间，以 HHMM 数字表示；departure[i] 属于 arrival[i]
- 返回值integer
- 同一分钟内车站停靠的列车数量最多时所需的最少站台数
约束条件
1 ≤ arrival.length == departure.length ≤ 50000 ≤ arrival[i] ≤ departure[i] ≤ 2359- 每个时间都是有效的
HHMM时间：它的最后两位数字最多为 59。 - 所有列车都在同一天运行。数组未排序。
示例
- 输入
- arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
- 输出
- 3
- 解释
- 15:30 时，车站有三列火车：一列从 15:00 到 16:00，一列从 15:20 到 15:35，还有一列从 15:30 到 15:45。没有任何一分钟有四列火车同时停靠，所以
3个站台就够了。
- 输入
- arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
- 输出
- 2
- 解释
- 12:30 到达的列车与 12:30 出发的列车相遇，13:00 时也会发生同样的情况。这两个时刻车站里各有两列火车，所以答案是
2，不是 1。
- 输入
- arrival = [600, 700, 1300]departure = [2200, 715, 1400]
- 输出
- 2
- 解释
- 06:00 到 22:00 的列车让一个站台全天都很忙。07:00 到 07:15 的列车和 13:00 到 14:00 的列车从不相遇，因此它们共用第二个站台：
2。
进阶
有些夜班列车在午夜前到达，午夜后出发，因此出发时间的数字比到达时间小。时刻表跨越午夜时，你会如何计算站台数量？
提示
逐个打开提示，每个都会多透露一点。
先暂时不考虑每趟列车使用哪个站台。随便选一天中的某一分钟：仅这一分钟就要求你有多少个站台？
车站的列车数量只会在列车到达时增加，在列车离开时减少。按时间顺序处理这些事件，并持续记录列车数量，最大的数量就是答案。如果时间相同，先处理到达事件，因为离开的列车在这一分钟内仍占用站台。
将到达时间和出发时间分别排序为两个列表，并各设置一个指针。如果下一个到达时间早于或等于下一个出发时间，就增加一列火车并记录峰值；否则就移除一列火车。到达时间用完后停止。
题解
答案是同一分钟内车站的列车最大数量。关键是找出列车最多的那一分钟，而不必比较每一对列车。分别对到站时间和离站时间排序，然后按时间顺序遍历当天的事件并持续统计列车数量，就能在 O(n log n) 时间内找到答案。
统计每个到站的列车数量
结果正确，但无法在最大的测试中运行完毕
思路
在同一分钟停靠的列车都需要不同的站台，所以最繁忙的一分钟是站台数的下限。这个数量也足够：只有当到站列车发现所有已开放的站台都被占用时，才开放一个新站台。在那一分钟，每个已开放的站台上都停着一列车，新站台上也停着一列车，因此开放的站台数永远不会超过高峰值。
在站列车的数量只会在列车到站时增加，因此最繁忙的一分钟就是某列车的到站分钟。对于每列列车 i，统计满足 arrival[j] ≤ arrival[i] ≤ departure[j] 的列车 j。两个比较都使用 ≤，因为列车在离开的那一分钟仍停在站台上。
每列 n 列车都要检查所有 n 列车，因此工作量为 O(n²)：5000 列列车需要进行 2500 万次成对检查。
算法
- 将
most = 0。 - 对于每列火车
i，统计满足arrival[j] ≤ arrival[i] ≤ departure[j]的火车j的数量。 - 如果该数量大于
most，就保存这个数量。 - 返回
most。
def minimumPlatforms(arrival, departure):
n = len(arrival)
most = 0
for i in range(n):
# trains standing at the station in the minute train i arrives
here = 0
for j in range(n):
if arrival[j] <= arrival[i] <= departure[j]:
here += 1
most = max(most, here)
return most对两个列表排序，并使用双指针遍历
思路
某一分钟在场的列车数量只取决于截至该分钟到达了多少列车、离开了多少列车，而不取决于哪列车在什么时候离开。因此，将到达时间和离开时间作为两个独立的列表分别排序。按时间顺序一起读取时，它们就是当天发生的事件：一列车到达，数量就加 1；一列车离开，数量就减 1。
如果时间相同，先处理到达事件，因为离开的列车在那一分钟仍占用站台。在第一个示例中，1100 时离开后，数量回到 0；接着，1500、1520 和 1530 时到达的列车都先于 1535 时的离开事件，因此数量达到 3。
到达事件处理完后，剩余的离开事件只会让数量减少，因此遍历可以在这里停止。排序的时间复杂度为 O(n log n)，遍历最多需要 2n 步。
算法
- 对
arrival的副本和departure的副本进行排序。 - 将
platforms、most、i和j设置为0。 - 当
i < n时：如果arrivals[i] ≤ departures[j]，就将platforms加 1，更新most，并将i向前移动。 - 否则，将
platforms减 1，并将j向前移动。 - 返回
most。
def minimumPlatforms(arrival, departure):
arrivals = sorted(arrival)
departures = sorted(departure)
n = len(arrivals)
platforms = 0 # trains at the station right now
most = 0
i = 0 # next arrival
j = 0 # next departure
while i < n:
if arrivals[i] <= departures[j]:
# the next event is an arrival; on a tie the leaving train is still there
platforms += 1
most = max(most, platforms)
i += 1
else:
platforms -= 1
j += 1
return most
易错点和边界情况
- 在需要包含边界时却用
<比较，而不是用≤。在第二个示例中，每列到达的火车都会使用同一分钟离开的火车所占用的站台，答案从 2 降到 1。 - 对
HHMM数字做减法：1300 减去 1259 等于 41，但这两个时间只相差一分钟。比较它们是安全的，而答案只进行比较。 - 按到达时间给火车排序，并且只将每列火车与它前面的那列比较。在第三个示例中，从 06:00 到 22:00 的长时间停留会与列表中靠后的火车重叠。
- 跳过在同一分钟到达并离开的火车。四列火车各自从 10:00 停到 10:00，也需要四个站台。
常见问题3
最少站台问题的时间复杂度是多少？
对两个数组进行排序需要 O(n log n)，之后的扫描需要 O(n)，因此排序占主导。排序后的副本需要额外的 O(n) 空间。
最少平台问题和会议室 II 有什么不同？
两者都要求找出同一时刻重叠的最多区间。这里，列车会一直占用站台，直到它离开的那一分钟；而在会议室 II 中，会议一结束，房间就空出来了。在扫描过程中，这只需一次比较：如果时间相同，这里先处理到达事件，而那里先处理结束的会议。
不排序也能解决最少站台问题吗？
是的，因为每次时间都符合固定的时钟格式。按 HHMM 数字对 2401 个计数器编索引，每次到达时加 1，并在 departure + 1 处减 1。最大的运行总和就是答案：时间复杂度为 O(n + 2400)。像 1260 到 1299 这样的索引不是有效的时钟时间，不会有到达事件，因此不会产生峰值。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def minimumPlatforms(arrival, departure):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
arrival = [900, 1500, 920, 1520, 1000, 1530] departure = [930, 1600, 1010, 1535, 1100, 1545]
预期输出
3