【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e801
【解題想法】排序，Greedy
- 把每天的課程分開排序，結束時間最早的排在前面（增加後面可多選別的課程的可能性），結束時間相同的話，把開始時間早的排在前面。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define pii pair<int,int>
vector <pii> v[5];
bool cmp(pii a, pii b){
if (a.second != b.second) return a.second < b.second;
else return a.first < b.first;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, D, S, T;
cin >> N;
for (int i=0; i<N; i++){
cin >> D >> S >> T;
D--;
v[D].push_back({S, T});
}
for (int i=0; i<5; i++){
sort(v[i].begin(), v[i].end(), cmp);
}
int ans = 0;
for (int i=0; i<5; i++){
int s = 0, e = 0;
for (auto j: v[i]){
if (j.first >= e) {
ans++;
s = j.first;
e = j.second;
}
}
}
cout << ans << '\n';
return 0;
}
Python code (credit: Amy Chou)
N = int(input())
a = [[] for _ in range(5)]
for _ in range(N):
D, S, T = map(int, input().split())
D -= 1
a[D].append((S, T))
for i in range(5):
a[i].sort(key=lambda x: (x[1], x[0]))
ans = 0
for i in range(5):
s = 0
e = 0
for (i, j) in a[i]:
if i >= e:
ans += 1
s = i
e = j
print(ans)