題目
有 n 個工作,給定 start time 和 end time,工作不能重疊,請問最多可以完成幾個工作?
解法
- end time 最早的工作先做。
- start time 早於正在執行工作的 end time,就放棄。
- start time 晚於或等於正在執行工作的 end time,就做。
Code
#include <iostream>
using namespace std;
struct job{
int s, e;
};
bool cmp(job a, job b){
return a.e < b.e;
}
int main(){
int n;
cin >> n;
job jb[n];
for(int i=0; i<n; i++)
cin >> jb[i].s >> jb[i].e;
sort(jb, jb+n, cmp);
int now = -1, ans = 0;
for(int i=0; i<n; i++){
if(jb[i].s >= now){
//如果該工作的st晚於或等於正在執行工作的et就做
ans++;
now = jb[i].e;
}
}
cout << ans << '\n';
}
5
1 10
2 4
3 6
2 5
4 9
output: 2