e801 - p8. 排課表
題目描述
題目要求找出在給定的課程表中，小新最多可以選修多少門不衝突的課程。每門課程有上課日期、開始時間和結束時間。
解題思路
這個問題可以使用貪心演算法解決。首先，按照課程的日期排序。對於每一天，按照課程的結束時間排序。然後，遍歷每一天的課程，選擇結束時間最早的課程，並將其加入到已選課程的集合中。對於後續的課程，如果其開始時間大於或等於前一個已選課程的結束時間，則選擇該課程。這樣可以確保在每一天選擇最多的不衝突課程。
複雜度分析
- 時間複雜度: O(n log n)，其中 n 是課程的數量。排序需要 O(n log n) 的時間，遍歷課程需要 O(n) 的時間。
- 空間複雜度: O(n)，用於儲存課程的結構體陣列。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
struct cls{
int begin;
int end;
int day;
};
bool cmp(cls x,cls y){
if(x.day==y.day){
if(x.end==y.end)
return x.begin<y.begin;
return x.end<y.end;
}
return x.day<y.day;
}
int main(){
int n,max,ans,maxd;
while(cin >> n){
max=0;ans=0;maxd=0;
cls a[n];
for(int i=0;i<n;i++)
cin >> a[i].day >> a[i].begin >> a[i].end ;
sort(a,a+n,cmp);
for(int i=0;i<n;i++){
//cout << a[i].day << " " << a[i].begin << " " << a[i].end << "\n";
if(a[i].day!=maxd){
maxd=a[i].day;
max=a[i].end;
ans++;
}
else if(a[i].begin>=max){
max=a[i].end;
ans++;
}
}
cout << ans << "\n";
}
}