HDU 4883: TIANKENG's Restaurant - 最少椅子數差分統計

問題描述

餐廳有 n 批客人，第 i 批有 X_i 人，到達時間 ST_i，離開時間 ED_i（格式 hh:mm）。每位客人佔一把椅子。若某批客人到達的同時另一批離開，椅子可立即重複使用。求最少需準備多少把椅子。

解題思路：時間軸差分 / 直接統計

一天共 24 × 60 = 1440 分鐘。將每組客人的到達、離開時間轉換為分鐘數 s、e。因為「到達與離開同分鐘可共用椅子」，離開分鐘 e 不計入佔用，故實際佔用區間為 [s, e-1]。

建立長度 1440 的陣列 time[]，對每組客人，在 time[s] 到 time[e-1] 區間各加上 X_i。最後掃描 time[] 找最大值即為答案。

複雜度

每測試案例 O(n × 平均用餐時長 + 1440)。n ≤ 10000，用餐時長 ≤ 1440，最壞約 1.4×10⁷ 操作，2 秒內輕鬆通過。

完整代碼

#include <cstdio>
#include <cstring>
using namespace std;

int timeArr[1442];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        memset(timeArr, 0, sizeof(timeArr));
        int n;
        scanf("%d", &n);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int cnt, sh, sm, eh, em;
            scanf("%d %d:%d %d:%d", &cnt, &sh, &sm, &eh, &em);
            int s = sh * 60 + sm;
            int e = eh * 60 + em - 1; // 離開分鐘不佔用
            for (int t = s; t <= e; ++t) {
                timeArr[t] += cnt;
            }
        }
        for (int t = 0; t < 1440; ++t) {
            if (timeArr[t] > ans) ans = timeArr[t];
        }
        printf("%d\n", ans);
    }
    return 0;
}