問題闡述

已知若干個工作的開始時間和結(jié)束時間，求最大兼容的活動個數(shù)。
舉例，如下四個活動
活 動i 1 2 3 4
開始時間 1 0 4 7
結(jié)束時間 3 2 2 5
可知活動1和2是不兼容的（活動1在活動2結(jié)束前便開始了）。
區(qū)間調(diào)度目標(biāo)就是需要找出可以最大兼容的活動數(shù)。

分析

容易想到的幾種貪心策略

• 最早開始時間：每次在未安排的工作中選擇開始時間最早（當(dāng)然必須滿足遲于最后一個工作的結(jié)束時間）加入工作流。預(yù)處理：將所有工作按開始時間升序排列。
• 最早結(jié)束時間：每次選擇結(jié)束時間最早的工作加入。預(yù)處理：將所有工作按結(jié)束時間升序排列。
• 最短工作區(qū)間：每次選擇耗時最短的工作加入。預(yù)處理：將所有工作按 結(jié)束時間-開始時間 大小升序排列。
• 最少沖突：對每個工作，計算與其沖突的工作數(shù)k，預(yù)處理：將所有工作按k升序排列。
  針對這些想法，可以舉例驗證是否存在明顯漏洞。下圖的例子可以看出最早開始時間、最短工作區(qū)間、最少沖突都不符合要求?？梢赃M一步證明，按最早結(jié)束時間貪心策略能找到最優(yōu)解。
  
  幾種貪心策略的推翻
  
  思想：將所有工作按結(jié)束時間進行升序排序，依次加入同時滿足以下兩個條件的工作
• 結(jié)束時間最早
• 開始時間晚于上一工作（已被調(diào)度的）結(jié)束時間

數(shù)據(jù)結(jié)構(gòu)

• 工作數(shù) n
• n個工作數(shù)的開始時間s[n], 結(jié)束時間t[n]。C++中可以用pair將兩個數(shù)據(jù)組合成一個數(shù)據(jù)，有點類似struct（其實pair確實是用struct構(gòu)造的）。
• 最大兼容工作數(shù)cnt
• 可兼容的工作序列job[n]
  預(yù)處理：將n個工作按結(jié)束時間升序排列（這里直接用了sort函數(shù)）。

代碼實現(xiàn)

#include <cstdio>
#include <iostream>
#include <utility>
#include <algorithm>

using namespace std;

const int maxn = 105;
pair<int, int> job[maxn];   

int main(){
    int n; cin >> n;
    for(int i=0;i<n;i++)
        cin >> job[i].first >> job[i].second;
    sort(job, job+n);
    int t=0, cnt=0;  //t表示上一被安排的工作的結(jié)束時間
    for(int i=0;i<n;i++){
        if(t<job[i].first){
            cnt++;
            t = job[i].second;
        }
    }
    cout << cnt;
    return 0;
}

Tips

• sort函數(shù)
  sort(first_pointer, first_pointer+N, cmp)
  first_pointer一般是數(shù)組名
  cmp可選，不填時默認(rèn)以升序排列，也可自定義cmp改變排序規(guī)則。如

bool cmp(int a, int b){
    return a>b;  //降序，其它數(shù)值類型同理
}

• pair對象
  構(gòu)造
  pair<int, string> p1(1, "Sun");
  p2 = make_pair(2, "Xun");
  元素
  pair.first
  pair.second