为何滑动窗口算法不适用于最小站台数问题？

错误原因 #

你的双指针滑动窗口逻辑存在核心缺陷：当按到达时间排序列车对后，发车时间是无序的。当前j指向的列车到达时，代码仅向前移动i直到mp[j].first <= mp[i].second，但这无法覆盖所有已经发车的列车——因为可能存在i之后的列车，其发车时间早于当前mp[i].second，这些列车已经释放了站台，却没被统计到，最终导致计算出的相交区间数（所需站台数）偏大。

这种滑动窗口逻辑仅适用于区间起始和结束都严格有序的场景，但你的排序方式只保证了到达时间有序，发车时间混乱，因此无法正确统计当前同时停靠的列车数量。

失败测试用例 #

以下是一个最小测试用例，会导致算法输出错误结果：

• 列车1：到达时间1，发车时间10
• 列车2：到达时间2，发车时间3
• 列车3：到达时间4，发车时间5

算法错误执行过程 #

1. 排序后列车顺序为：(1,10)、(2,3)、(4,5)
2. j=0：mxi=1，j自增到1
3. j=1：mp[1].first=2 不大于 mp[0].second=10，不移动i，mxi=max(1, 1-0+1)=2，j自增到2
4. j=2：mp[2].first=4 不大于 mp[0].second=10，不移动i，mxi=max(2,2-0+1)=3
5. 最终返回3，但实际所需最小站台数为2（列车2在3点发车，列车3到达时仅列车1和3同时停靠）

代码问题点 #

你的排序函数comp虽然定义了，但实际调用sort(mp.begin(), mp.end())时并未传入该自定义比较器（不过C++默认的pair排序逻辑和comp一致，所以这不是核心问题）。真正的错误出在双指针的移动逻辑：没有考虑排序后发车时间的无序性，无法正确筛选出所有已发车的列车，导致统计的同时停靠列车数失真。

内容的提问来源于stack exchange，提问作者BlazeRod11