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