ZeroJudge 解題筆記：f731. 老鼠的直播間

作者：王一哲
日期：2025年10月22日


ZeroJudge 題目連結：f731. 老鼠的直播間

解題想法

這題與 APCS實作題2016年3月第3題：線段覆蓋長度 解題觀念相同，將所有時段的開始時間 start 與 1 組合成數組，結束時間 end 與 -1 組合成數組，將數組加到串列之中，再依照時間排序。接下來依序讀取時間，更新目前線上的人數及最大值。

Python 程式碼

使用時間約為 1.8 s，記憶體約為 46.8 MB，通過測試。

n = int(input())  # n 個時段
segs = []  # 時刻與人數變化，(start, 1) 或 (end, -1)
for _ in range(n):  # 讀取 n 行資料
    start, end = map(int, input().split())
    segs += [(start, 1), (end, -1)]
segs.sort()  # 依照時刻排序
cnt, imax = 0, 0  # 目前的人數，最多人數
for t, c in segs:  # 依序讀取時刻與人數變化
    cnt += c  # 更新人數
    imax = max(imax, cnt)  # 更新 imax
print(imax) 

C++ 程式碼

使用時間約為 72 ms，記憶體約為 3.3 MB，通過測試。

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
    int n; scanf("%d", &n);
    vector<pair<int, int>> segs (n+n);
    for(int i=0; i<n; i++) {
        int start, end; scanf("%d %d", &start, &end);
        segs[2*i] = make_pair(start, 1);
        segs[2*i + 1] = make_pair(end, -1);
    }
    sort(segs.begin(), segs.end());
    int cnt = 0, imax = 0;
    for(auto seg : segs) {
        int c = seg.second;
        cnt += c;
        imax = max(imax, cnt);
    }
    printf("%d\n", imax);
    return 0;
}