一道算法编程题

火车站台数量

• 描述：假设已知某个火车站的所有过往列车的到达arrival和离开departure时间（同一天），如果要求所有列车都不等待直接进站，问至少需要多少个站台。无需考虑晚点等特殊情况。

• 输入：

第一行输入一个正整数N，$1 \le N \le 100$，表示过往列车数。

第二行输入N个字符串，每个字符串表示列车的到达时间，字符串之间用空格隔开。

第三行输入N个字符串，每个字符串表示列车的离开时间，字符串之间用空格隔开。

• 输出：

输出一个整数，表示最少需要的站台数。

• 样例输入：

6
9:00 9:40 9:50 11:00 15:00 18:00
9:10 12:00 11:20 11:30 19:00 20:00

• 样例输出：

3

• 样例解释：

最多有3辆列车同时进站（在11:00到11:20之间），所以至少需要3个火车站台。

• 解题思路：

题目要求找到所有时间中同时在车站的列车的最大数量。一个简单的方案是逐个检查每个车辆的停发时间段，然后看有多少个时间段区间与其有重合，记录最多的重合区间数目，即为待求解的答案。易知，此方法的时间复杂度为O(n^2)。
认真思考后，其实可以有O(nlog_2 n)时间复杂度的方法。思路是将所有的事件 (到达或离开)按时间顺序排序，然后只记录当前还在车站（未离开的）列车。所有时间点中最多数量列车即待求解的答案。
例如，对于上面样例输入，将所有事件按时间排序后得到：

时间	事件	需要的站台数量
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，时间段为11:00 ~ 11:20

注意，在算法实现时，只需对到达时间arr数组，和离开时间dep数组进行单独排序，然后将两个有序数组再进行归并操作。

• 参考代码:

  #include<iostream>
  #include<algorithm>
  
  using namespace std;
  
  
  int main() {
      
      return 0;
  }