Greedy 工作排程:n個工作,求最多完成幾個工作

0 Shares
0
0
0

題目

有一台機器,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; //end time 較早的排在前面
}

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){
        /*如果該工作的start time
        等於或晚於
        正執行工作的end time
        就執行該工作*/
            ans++;
            now = jb[i].e;
        }
    }
    cout << ans << '\n';
}

/*
5
1 10
2 4
3 6
2 5
4 9

output: 2
*/

分享文章
0 Shares
發佈留言

發佈留言必須填寫的電子郵件地址不會公開。