ZeroJudge 解題筆記：k397. 會議安排 (Meeting)

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



ZeroJudge 題目連結：k397. 會議安排 (Meeting)

解題想法

解題時要注意，測資中某些時段會相連，例如輸入範例 4 的 [72, 147] 及 [147, 161]，要合併為 [72, 161]。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # 兩個人有空的時段數量
    a, b = [], []  # 阿明、阿文有空的時段
    for _ in range(n):  # 讀取 n 行資料
        s, e = map(int, input().split())  # 開始、結束時間 [s, e]
        if a and s == a[-1][1]: a[-1][1] = e  # 如果 a 有資料而且 s 等於最後一個結束時間，更新為 e
        else: a.append([s, e])  # 否則將 [s, e] 加入 a
    for _ in range(m):  # 讀取 m 行資料
        s, e = map(int, input().split())  # 開始、結束時間 [s, e]
        if b and s == b[-1][1]: b[-1][1] = e  # 如果 b 有資料而且 s 等於最後一個結束時間，更新為 e
        else: b.append([s, e])  # 否則將 [s, e] 加入 b
    d = int(input())  # 需要的時間長度
    n, m = len(a), len(b)  # 更新 n, m
    i, j, can = 0, 0, False  # 從 a, b 讀取資料的索引值，是否有解
    while i < n and j < m:  # 當 i, j 都還沒有出界
        if a[i][1] < b[j][0]: i += 1  # a 的結束時間小於 b 的開始時間，i 加 1
        elif b[j][1] < a[i][0]: j += 1  # b 的結束時間小於 a 的開始時間，j 加 1
        elif a[i][0] <= b[j][0] <= a[i][1] or b[j][0] <= a[i][0] <= b[j][1]:  # a, b 有交集
            s, e = max(a[i][0], b[j][0]), min(a[i][1], b[j][1])  # 開始時間取大的，結束時間取小的
            if e - s >= d:  # 如果交集時間夠長，印出 s, s+d，有解，中止迴圈
                print(s, s+d); can = True; break
            if a[i][1] <= b[j][1]: i += 1  # 如果 a 的結束時間較早，i 加 1
            else: j += 1  # 反之，j 加 1
    if not can: print(-1)  # 如果無解，印出 -1

C++ 程式碼

使用時間約為 2 ms，記憶體約為 288 kB，通過測試。

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

int main() {
    int n, m;  // 兩個人有空的時段數量
    while(scanf("%d %d", &n, &m) != EOF) {
        vector<pair<int, int>> a, b;  // 阿明、阿文有空的時段
        for(int i=0; i<n; i++) {  // 讀取 n 行資料
            int s, e; scanf("%d %d", &s, &e);  // 開始、結束時間 [s, e]
            if (!a.empty() && s == a.back().second) a.back().second = e;  // 如果 a 有資料而且 s 等於最後一個結束時間，更新為 e
            else a.push_back(make_pair(s, e));  // 否則將 [s, e] 加入 a
        }
        for(int i=0; i<m; i++) {  // 讀取 m 行資料
            int s, e; scanf("%d %d", &s, &e);  // 開始、結束時間 [s, e]
            if (!b.empty() && s == b.back().second) b.back().second = e;  // 如果 b 有資料而且 s 等於最後一個結束時間，更新為 e
            else b.push_back(make_pair(s, e));  // 否則將 [s, e] 加入 b
        }
        int d; scanf("%d", &d);  // 需要的時間長度
        n = (int)a.size(); m = (int)b.size();  // 更新 n, m
        int i = 0, j = 0;  // 從 a, b 讀取資料的索引值
        bool can = false;  // 是否有解
        while(i < n && j < m) {  // 當 i, j 都還沒有出界
            if (a[i].second < b[j].first) i++;  // a 的結束時間小於 b 的開始時間，i 加 1
            else if (b[j].second < a[i].first) j++;  // b 的結束時間小於 a 的開始時間，j 加 1
            else if ((b[j].first >= a[i].first && b[j].first <= a[i].second) || 
                     (a[i].first >= b[j].first && a[i].first <= b[j].second)) {  // a, b 有交集
                int s = max(a[i].first, b[j].first), e = min(a[i].second, b[j].second);  // 開始時間取大的，結束時間取小的
                if (e - s >= d) {  // 如果交集時間夠長，印出 s, s+d，有解，中止迴圈
                    printf("%d %d\n", s, s+d); can = true; break;
                }
                if (a[i].second <= b[j].second) i++;  // 如果 a 的結束時間較早，i 加 1
                else j++;  // 反之，j 加 1
            }
        }
        if (!can) printf("-1\n");  // 如果無解，印出 -1
    }
    return 0;
}