ZeroJudge 解題筆記：e801. p8. 排課表

作者：王一哲
日期：2025年2月5日



ZeroJudge 題目連結：e801. p8. 排課表

解題想法

這題考貪心法，先將課程依照結束時間由小到大排序，再依序讀取課程是星期幾 w、開始時間 s、結束時間 e，如果星期 w 還沒有選課則加入 (s, e)；如果已經選課而且 s 大於等於 chose[w] 最後一項結束時間，可以選課。

Python 程式碼

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

import sys

for line in sys.stdin:
    N = int(line)  # N 種課程
    course = [list(map(int, input().split())) for _ in range(N)]  # 讀取 N 行
    course.sort(key = lambda x : x[2])  # 依照結束時間由小到大排序
    chose = [[] for _ in range(6)]  # 一週內每天可以的課程開始、結束時間
    for w, s, e in course:  # 依序由 course 讀取課程是星期幾 w、開始時間 s、結束時間 e
        if not chose[w]:  # 如果星期 w 還沒有選課
            chose[w] = [(s, e)]  # 加入 (s, e)
        elif s >= chose[w][-1][1]:  # 如果 s 大於等於 chose[w] 最後一項結束時間，可以選課
            chose[w].append((s, e))  # 加入 (s, e)
    print(sum([len(ch) for ch in chose]))  # 將 chose 所有的項目數量加起來

C++ 程式碼

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

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; // N 種課程
    while(cin >> N) {    
        vector<vector<int>> course (N, vector<int> (3));  // 讀取 N 行課程資料
        for(int i=0; i<N; i++) cin >> course[i][0] >> course[i][1] >> course[i][2];
        sort(course.begin(), course.end(), [] (vector<int> a, vector<int> b) {
            return a[2] < b[2]; } );  // 依照結束時間由小到大排序
        vector<vector<pair<int, int>>> chose (6);  // 一週內每天可以的課程開始、結束時間
        for(auto ch : course) {  // 依序由 course 讀取課程是星期幾 w、開始時間 s、結束時間 e
            int w = ch[0], s = ch[1], e = ch[2];
            if (chose[w].empty()) {  // 如果星期 w 還沒有選課
                chose[w].push_back(make_pair(s, e));  // 加入 (s, e)
            } else if (s >= chose[w].back().second) {  // 如果 s 大於等於 chose[w] 最後一項結束時間，可以選課
                chose[w].push_back(make_pair(s, e));  // 加入 (s, e)
            }
        }
        int total = 0;  // 選課數量
        for(int i=1; i<=5; i++) total += (int)chose[i].size();  // 將 chose 所有的項目數量加起來
        cout << total << "\n";
    }
    return 0;
}