Greedy 工作排程

題目

有 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
發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *