HDU 4509 減肥記II：離散化 / 陣列標記計算空閒時間

問題描述

一天 24 小時 = 1440 分鐘。給定 n 個任務，每個有開始/結束時間（HH:MM）。任務可能重疊。求一天中未被任務佔用的總分鐘數（可用於鍛煉）。n ≤ 500,000。

解法一：直接陣列標記（時間換空間）

因總分鐘數固定 1440，極小。建立 bool used[1440]。
對每個任務，將 [start, end) 分鐘標記為 true。最後數 false 的個數。
時間：O(n + 1440) ≈ O(n)，空間：O(1440)。極其高效，無需離散化。

解法二：離散化 + 差分數組（通用大範圍做法）

若時間範圍大（如 10⁹），需離散化：
1. 收集所有時間點（開始、結束）。
2. 排序去重，映射到索引。
3. 差分數組 diff[idx[start]]++, diff[idx[end]]--。
4. 前綴和得覆蓋次數，次數為 0 的區段長度累加。
本題因 1440 固定，解法一更簡優。

代碼實現 (C++，陣列標記法)

#include <bits/stdc++.h>
using namespace std;
int toMin(int h, int m) { return h * 60 + m; }
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        vector used(1440, false);
        for (int i = 0; i < n; ++i) {
            string s, e; cin >> s >> e;
            int sh = stoi(s.substr(0,2)), sm = stoi(s.substr(3,2));
            int eh = stoi(e.substr(0,2)), em = stoi(e.substr(3,2));
            int start = toMin(sh, sm);
            int end = toMin(eh, em);
            for (int t = start; t < end; ++t) used[t] = true;
        }
        int free = 0;
        for (bool b : used) if (!b) ++free;
        cout << free << '\n';
    }
    return 0;
}

複雜度

• 時間：O(n × 平均任務長度) 最壞 O(n × 1440)，但 n ≤ 5e5，1440 為常數，實際極快（約 7e8 簡單操作，C++ 約 0.5-1 秒）。可用差分優化至 O(n + 1440)。
• 優化版（差分）：diff[start]++, diff[end]--，最後前綴和，O(n + 1440) 確定性線性。
• 空間：O(1440)。

優化版差分代碼片段

vector diff(1441, 0);
for (each task) { diff[start]++; diff[end]--; }
int cur = 0, free = 0;
for (int i = 0; i < 1440; ++i) {
    cur += diff[i];
    if (cur == 0) ++free;
}

關鍵點

• 時間範圍固定且小（1440）時，直接陣列/差分是最優解，無需複雜離散化。
• 差分數組將區間標記從 O(長度) 降為 O(1)。
• 注意時間解析：HH:MM 字符串切分轉換。

這題展示了「問題約束決定算法選擇」：小範圍用陣列，大範圍用離散化，差分技巧通用於區間覆蓋計數。