火車站臺數(shù)量問題
假設(shè)已知某個火車站的所有過往列車的到達(dá)arrival和離開departure時間（同一天），如果要求所有列車都不等待直接進(jìn)站，問至少需要多少個站臺。無需考慮晚點(diǎn)等特殊情況。
例如，
Input：
到達(dá)時間： arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
離開時間： dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Output：
3 （最多有3輛列車同時進(jìn)站（在11:00到11:20之間））
解題思路
題目要求找到所有時間中同時在車站的列車的最大數(shù)量。一個簡單的方案是逐個檢查每個車輛的停發(fā)時間段，然后看有多少個時間段區(qū)間與其有重合，記錄最多的重合區(qū)間數(shù)目，即為待求解的答案。易知，此方法的時間復(fù)雜度為O(n^2)。
認(rèn)真思考后，其實(shí)可以有O(nlog_2 n)時間復(fù)雜度的方法。思路是將所有的事件 (到達(dá)或離開)按時間順序排序，然后只記錄當(dāng)前還在車站（未離開的）列車。所有時間點(diǎn)中最多數(shù)量列車即待求解的答案。
例如，對于上面樣例輸入，將所有事件按時間排序后得到：
| 時間 | 事件 | 需要的站臺數(shù)量 |
|---|---|---|
| 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 |
最多需要的站臺數(shù)量是3，時間段為11:00~11:20
注意，在算法實(shí)現(xiàn)時，只需對到達(dá)時間arr數(shù)組，和離開時間dep數(shù)組進(jìn)行單獨(dú)排序，然后將兩個有序數(shù)組再進(jìn)行歸并操作。
