题目描述：

有n项工作，每项工作分别在si时间开始，ti时间结束。对于每项工作，你都可以选择参加或不参加，但选择了参加某项工作就必须至始至终参加全程参与，即参与工作的时间段不能有重叠(即使开始的瞬间和结束的瞬间重叠也是不允许的)。

你的目标是参与尽可能多的工作，那么你最多能参与多少项工作呢？

限制条件：

1<=n<=100000

1<=si<=ti,=10^9

这个问题首先想到的就是贪心算法。但设计算法时容易出现错误。

比较容易想到的算法如：

• 在可选工作中，每次选取最先开始的工作
• 在可选工作中，每次选取用时最短的工作
• 在可选工作中，每次选取与最少可选工作有重叠的工作
• 在可选工作中，每次选取结束时间最早的工作

而很显然，前三项算法都不具有普适性（例如：一项开头早，持续时间长的工作和两项开头晚的工作）。

关于最后一种算法的解释：

结束时间早，对应的可选工作就越多。当然也可以用归纳法来证明。

代码实现：

#include 
#include 
#include 
#include 
using namespace std;

const int N = 5;
int s[N]={1,2,4,6,8};
int t[N]={3,5,7,9,10};

int solve()
{
pair itv[N];
for(int i = 0; i 
原文标题：区间调度问题|落絮飞雁的个人网站
原文链接：https://www.luoxufeiyan.com/2014/12/29/%e5%8c%ba%e9%97%b4%e8%b0%83%e5%ba%a6%e9%97%ae%e9%a2%98/
授权协议：创作共用 署名-非商业性使用 2.5 中国大陆
除注明外，本站文章均为原创；转载时请保留上述链接。