不带权重的区间调度问题——动态规划、贪心算法

问题阐述

已知若干个工作的开始时间和结束时间，求最大兼容的活动个数。
举例，如下四个活动
活 动i 1 2 3 4
开始时间 1 0 4 7
结束时间 3 2 2 5
可知活动1和2是不兼容的（活动1在活动2结束前便开始了）。
区间调度目标就是需要找出可以最大兼容的活动数。

分析

容易想到的几种贪心策略

• 最早开始时间：每次在未安排的工作中选择开始时间最早（当然必须满足迟于最后一个工作的结束时间）加入工作流。预处理：将所有工作按开始时间升序排列。
• 最早结束时间：每次选择结束时间最早的工作加入。预处理：将所有工作按结束时间升序排列。
• 最短工作区间：每次选择耗时最短的工作加入。预处理：将所有工作按 结束时间-开始时间 大小升序排列。
• 最少冲突：对每个工作，计算与其冲突的工作数k，预处理：将所有工作按k升序排列。
  针对这些想法，可以举例验证是否存在明显漏洞。下图的例子可以看出最早开始时间、最短工作区间、最少冲突都不符合要求。可以进一步证明，按最早结束时间贪心策略能找到最优解。
  几种贪心策略的推翻
  思想：将所有工作按结束时间进行升序排序，依次加入同时满足以下两个条件的工作
• 结束时间最早
• 开始时间晚于上一工作（已被调度的）结束时间

数据结构

• 工作数 n
• n个工作数的开始时间s[n], 结束时间t[n]。C++中可以用pair将两个数据组合成一个数据，有点类似struct（其实pair确实是用struct构造的）。
• 最大兼容工作数cnt
• 可兼容的工作序列job[n]
  预处理：将n个工作按结束时间升序排列（这里直接用了sort函数）。

代码实现

#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表示上一被安排的工作的结束时间
    for(int i=0;i<n;i++){
        if(t<job[i].first){
            cnt++;
            t = job[i].second;
        }
    }
    cout << cnt;
    return 0;
}

Tips

• sort函数
  sort(first_pointer, first_pointer+N, cmp)
  first_pointer一般是数组名
  cmp可选，不填时默认以升序排列，也可自定义cmp改变排序规则。如

bool cmp(int a, int b){
    return a>b;  //降序，其它数值类型同理
}

• pair对象
  构造
  pair<int, string> p1(1, "Sun");
  p2 = make_pair(2, "Xun");
  元素
  pair.first
  pair.second