HDU 1050 Moving Tables：走廊區間重疊計數求最小搬運時間

問題描述

走廊兩側各 200 個房間（北側奇數 1,3,...,399；南側偶數 2,4,...,400），房間對面相對。搬運一張桌子從房間 s 到 t 需 10 分鐘，佔用走廊區間 [min(s,t), max(s,t)]。同一時間內，區間不重疊的搬運可並行。每個房間最多一張桌子搬入或搬出。求完成所有搬運的最少總時間（分鐘）。

關鍵建模：區間重疊深度

每次搬運佔用走廊的一段區間。並行條件：區間不重疊。因此，最少時間槽數 = 最大區間重疊深度（即某個走廊位置被最多多少個區間覆蓋）。總時間 = 深度 × 10。

座標轉換技巧

走廊實際可用區間為房間門口之間的段。為統一處理：

• 若起點 s 為偶數（南側），其門口實際影響對面北側區間，故 s--。
• 若終點 t 為奇數（北側），同理 t++。
• 統一後，所有搬運區間為 [min(s,t), max(s,t)]，且端點均為奇數（北側門口）。

例如：10→20（偶→偶）→ 9→21；1→3（奇→奇）→ 1→3。

差分數組/掃描線計數

走廊長度固定（400），可用長度 401 的數組 cnt[401]：

for each move (s,t):
    if (s > t) swap(s,t);
    if (s%2==0) s--;
    if (t%2==1) t++;
    for i = s to t: cnt[i]++;
maxOverlap = max(cnt[i]);
answer = maxOverlap * 10;

複雜度

• 時間：O(N × L)，L=400 為常數，實際 O(N)。
• 空間：O(L) = O(1)。

樣例驗證

輸入：
3
4
10 20
30 40
50 60
70 80
2
1 3
2 200
3
10 100
20 80
30 50

輸出：
10
20
30

第三組：三條區間兩兩重疊，最大深度 3，時間 30 分鐘。

總結

本題是區間調度的經典變體：最少並行時間槽 = 最大區間重疊數。座標統一轉換（偶→奇）是關鍵技巧，將雙側走廊統一為單側離散點計數。代碼極短，思維清晰，是掃描線入門佳例。