ZeroJudge 解題筆記：n508.區間分割演算法練習

作者：王一哲
日期：2026年10月1日


ZeroJudge 題目連結：n508.區間分割演算法練習

解題想法

這題給一個正整數 $N$ 代表有 $N$ 場演講，接下來 $N$ 行，每行的格式皆為以下的樣子

Lecture 1: 9:10-10:00

如果演講的時段重疊，需要多用一間教室。如果某一場演講結束，另一場演講正好開始，可以使用同一間教室，不需要考慮換場的時間。要計算這 $N$ 場演講至少需要使用幾間教室。

這題困難之處在於讀取演講的開始、結束時間，因為測資不是用空格分隔時間，而是用 : 及 - 分隔時間。如果用 Python 解題，可以將字串讀進來之後，再用 split 分割字串，切出開始、結束時間的時、分，語法為

split('-')
split(':')

如果用 C++ 解題，假設演講編號，開始時間的時、分，結束時間的時、分，分別存入變數 k, ha, ma, hb, mb，則可以用 scanf 依照指定的格式讀取資料。為了避開前一行留下的換行符號， Lecture 之前要加一個空格，語法為

scanf(" Lecture %d: %d:%d-%d:%d", &k, &ha, &ma, &hb, &mb);

如果用 cin 讀取資料並存入字串 $s$，則要再從 $s$ 依序讀取字元，依照字元判斷是否需要分割資料，再將分割後的資料轉成 int 存入對應的變數之中。

接下來用掃瞄線演算法解題。為了便於排序及計算教室數量，用一個陣列 $arr$ 儲存開始、結束時間，將時間單位換成分，加入 $arr$ 的資料為

(開始時間, 1)
(結束時間, -1)

讀取完 $N$ 場演講的時間之後用 sort 由小到大排序。定義答案 $ans = 0$、目前使用的教室數量 $curr = 0$。從 $arr$ 之中依序讀取資料，更新目前同時進行的演講數量，也就是目前使用的教室數量 $curr$，再用 max 更新 $ans$。

Python 程式碼

解題時間約為 0.4 s，使用記憶體約為 47 MB。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        N = int(data[ptr])
        ptr += 3
        time = []
        for _ in range(N):
            s = data[ptr]
            ptr += 3
            a, b = s.split('-')
            ha, ma = map(int, a.split(':'))
            hb, mb = map(int, b.split(':'))
            time += [(ha * 60 + ma, 1), (hb * 60 + mb, -1)]
        time.sort()
        ans, curr = 0, 0
        for _, d in time:
            curr += d
            ans = max(ans, curr)
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

解題時間約為 48 ms，使用記憶體約為 4.8 MB。

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

int main() {
    int N;
    while(scanf("%d", &N) != EOF) {
        vector<pair<int, int>> arr(2 * N);
        for(int i = 0; i < N; i++) {
            int k, ha, ma, hb, mb;
            scanf(" Lecture %d: %d:%d-%d:%d", &k, &ha, &ma, &hb, &mb);
            arr[2*i] = {ha * 60 + ma, 1};
            arr[2*i + 1] = {hb * 60 + mb, -1};
        }
        sort(arr.begin(), arr.end());
        int ans = 0, curr = 0;
        for(auto it : arr) {
            curr += it.second;
            ans = max(ans, curr);
        }
        printf("%d\n", ans);
    }
    return 0;
}

解題時間約為 34 ms，使用記憶體約為 4.8 MB。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N;
    while(cin >> N) {
        vector<pair<int, int>> arr(2 * N);
        for(int i = 0; i < N; i++) {
            string x, y, s, t;
            cin >> x >> y >> s;
            s += "-";
            int parts[4], idx = 0;
            for(char c : s) {
                if (c == ':' || c == '-') {
                    parts[idx] = stoi(t);
                    idx++;
                    t.clear();
                } else {
                    t += c;
                }
            }
            arr[2*i] = {parts[0] * 60 + parts[1], 1};
            arr[2*i + 1] = {parts[2] * 60 + parts[3], -1};
        }
        sort(arr.begin(), arr.end());
        int ans = 0, curr = 0;
        for(auto it : arr) {
            curr += it.second;
            ans = max(ans, curr);
        }
        cout << ans << "\n";
    }
    return 0;
}