善良先生

用户名：Officialmomo

访问量：23528

签　名：

此时已莺飞草长，爱的人正在路上

等　　级
排　　名	167
经　　验	7061
参赛次数	8
文章发表	42
年　　龄	0
在职情况	学生
学　　校	东莞理工学院
专　　业	计算机科学与技术

　　自我简介：

穿越人海只为与你相拥

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

区间调度问题的贪心策略

　　作者: 善良先生　　　　发表时间：2019-12-14 18:31:24 浏览：325　|　评论：0　

感觉很久没正儿八经的写博客了，所以今天打算开始写一篇，今天准备的话题是区间调度问题的贪心策略

------------

贪心策略的原理不难，但是要想构思出一个正确无误的策略并不是很容易，需要自己的推到和简单证明，善于举出反例，多考虑情况才能写出完全正确的贪心算法

值得一提的是，贪心策略总是跟排序脱不开关系的。

### 区间调度的贪心策略
我所讲的例题来自于《挑战程序设计竞赛》，感兴趣的同学可以翻阅此书。

题目要求给出每个任务的开始时间和结束时间，目的是参与尽可能多的任务，问最多能够参与多少项工作？
为了方便，我从另外一个作者那儿copy来了样例图，顺便可以看看他的博客[区间调度问题](https://blog.csdn.net/Wangpeiyi9979/article/details/93537340 "区间调度问题")

![](/image_editor_upload/20191214062837_35372.png)

下面是我的代码，跟书上稍微不一样。。我是直接用map自动排序。。书上是用pair然后再sort函数排序。

```cpp
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <map>
using namespace std;
const int maxn = 1000;
int n;
int s[maxn],t[maxn];

int main(){
	cin>>n;
	int sum = 0,T = 0;
	int i,j;
	map<int,int> m;
	map<int,int>::iterator it;
	for(i = 1;i<=n;i++)
		cin>>s[i];
	for(i = 1;i<=n;i++)
		cin>>t[i];
	for(i = 1;i<=n;i++){
		pair<int,int> p(t[i],s[i]);
		m.insert(p);
	}
	for(it=m.begin();it!=m.end();it++){
		if(T<it->second){
			sum++;
			T = it->first;
		}
	}
	cout<<sum<<endl;
	return 0;
}
/*
5
1 2 4 6 8
3 5 7 9 10

*/
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

善良先生

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

亲和的解法

小九九（C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

区间调度问题的贪心策略

评论区

精彩推荐

买不到的数目（C++代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

WU-复数求和（C++代码）

用筛法求之N内的素数。（C++代码）

蛇行矩阵（C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

Tom数（C语言代码）

Tom数（C语言代码）

善良先生

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

亲和的解法

小九九 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

区间调度问题的贪心策略

评论区

精彩推荐

买不到的数目 （C++代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

WU-复数求和 （C++代码）

用筛法求之N内的素数。 （C++代码）

蛇行矩阵 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

Tom数 （C语言代码）

Tom数 （C语言代码）

小九九（C语言代码）

　　评论区

买不到的数目（C++代码）

WU-复数求和（C++代码）

用筛法求之N内的素数。（C++代码）

蛇行矩阵（C语言代码）

Tom数（C语言代码）

Tom数（C语言代码）