1. 最多有幾個工作可以執行 Solution

貪婪準則是將結束時間最早的工作先做，讓機器可以空下來準備做其他工作。先將n個工作以結束時間較早的工作排在前面，利用此原則排序好n個工作。

(1)由最前面取出第一個工作，工作取出後表示這個工作送入機器執行，可以執行的工作數增加1。

(2)所有剩餘的工作中，若開始時間早於正在執行工作的結束時間，就放棄執行這些工作，直到找到開始時間等於或晚於正在執行工作的結束時間，將找到的工作放入機器執行，可以執行的工作數增加1。

(3)繼續將所有剩餘的工作中，若開始時間早於正在執行工作的結束時間，就放棄執行這些工作，直到找到開始時間等於或晚於正在執行工作的結束時間，將找到的工作放入機器執行，可以執行的工作數增加1。

(4)不斷測試到n個工作檢查完，就可以獲得最多可以完成的工作數。

#include <bits/stdc++.h>
using namespace std;

struct Job{
    int startTime, endTime;
}job[105];
// 最多 100 個 Job
// job[i].startTime 代表第i個job開始時間
// job[i].endTime 代表第i個job結束時間

int N;
bool cmp( Job A, Job B ){
    return A.endTime < B.endTime;
}

int main(){

    while ( cin >> N ){
        for ( int i = 0 ; i < N ; i++ )
            cin >> job[i].startTime >> job[i].endTime;

        sort( job, job+N , cmp );

        int ans = 1, finishTime = job[0].endTime;


        for ( int i = 1 ; i < N ; i++ ){
            if ( job[i].startTime >= finishTime ){
                ans++;
                finishTime = job[i].endTime;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

另一版本程式

#include<iostream>
#include<algorithm>
using namespace std;

//工作的struct
struct Job{
  int start; //開始時間
  int end;   //結束時間
};

//任務結束時間越早的排越前面
bool cmp(Job a,Job b){
  return a.end<b.end;
}

int main(){

  int n,now,ans;
  Job job[101];

  while(cin>>n){

    //輸入n項工作的開始與結束時間
    for(int i=0;i<n;i++){
      cin >> job[i].start>>job[i].end; 
    }

    //按照任結束時間排序，結束時間越早越前面
    sort(job,job+n,cmp);

    ans=0; //能做的任務數量初始化
    now=-1;

    //貪婪演算法
    for(int i=0;i<n;i++){
      if (now<=job[i].start){ //這個工作的任務開始時間比目前時間還晚才能執行這個工作
        ans++;                //能做的工作數量+1
        now=job[i].end;       //下一個任務的開始時間不能比目前這個工作的結束時間早
      }
    }
    cout << ans << endl;
  }
}