落絮飞雁的个人网站

顺流而下,把梦做完

区间调度问题

题目描述:

有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 < N; i ++) {
itv[i].first = s[i];
itv[i].second = t[i];
}
sort(itv, itv + N);
int count = 0;
int t = 0;
for(int i = 0; i < N; i ++) {
if(t < itv[i].first) {
count ++;
t = itv[i].second;
}
}
return count;
}

int main() {
cout << solve() << endl;
return 0;
}

原文标题:区间调度问题|落絮飞雁的个人网站
原文链接: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 中国大陆
除注明外,本站文章均为原创;转载时请保留上述链接。