文档章节

贪心算法——区间调度问题

自由的角马
 自由的角马
发布于 2015/01/10 13:56
字数 1053
阅读 95
收藏 1

贪心算法——区间调度问题

 

问题主题:区间调度问题

问题描述:

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

限制条件:

1<=n<=100000

1<=si<=ti,=109

样例:

输入

n=5

s={1,2,4,6,8}

T={3,5,7,9,10}

输出

3(选择工作1, 3, 5)

 

 

解题分析:

对这个问题,如果使用贪心算法的话,可能有以下几种考虑:

(1)、每次选取开始时间最早的;

(2)、每次选取结束时间最早的;

(3)、每次选取用时最短的;

(4)、在可选工作中,每次选取与最小可选工作有重叠的部分;

对于上面的四种算法,只有算法(2)是正确的,其它的三种都可以找到相应的反例。具体证明如下:

 

数轴上有n个区间,选出最多的区间,使得这些区间不互相重叠。

算法:

将所有区间按右端点坐标从小到大排序,顺序处理每个区间。如果它与当前已选的所有区间都没有重叠,则选择该区间,否则不选。

证明:

显然,该算法最后选出的区间不互相重叠,下面证明所选出区间的数量是最多的。fi为该算法所接受的第i个区间的右端点坐标,gi为某最优解中的第i个区间的右端点坐标。

命题1.1  当i>=1时,该算法所接受的第i个区间的右端点坐标fi<=某最优解中的第i个区间的右端点坐标gi

该命题可以运用数学归纳法来证明。对于i=1,命题显然为真,因为算法第一个选择的区间拥有最小右端点坐标。令i>1,假定论断对i-1为真,即fi-1<=gi-1则最优解的第i个可选区间所组成的集合包含于执行该算法时第i个可选区间所组成的集合;而当算法选择第i个区间时,选的是在可选区间中右端点坐标最小的一个,所以有fi<=gi。证毕。

设该算法选出了k个区间,而最优解选出了m个区间。

命题1.2  最优解选出的区间数量m=该算法选出的区间数量k

假设m>k,根据命题1.1,有fk<=gk。由于m>k,必然存在某区间,在gk之后开始,故也在fk之后开始。而该算法一定不会在选了第k个区间后停止,还会选择更多的区间,产生矛盾。所以m<=k,又因为m是最优解选出区间个数,所以m=k

综上所述,算法选出的区间是最优解。

 

程序实现:

 

C++

#include <stdio.h>

#include <tchar.h>

#include <queue>

#include "iostream"

 

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<intint> 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;

}

Java

package greed;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: shihuichao
 * Date: 14-1-14
 * Time: 下午10:43
 * To change this template use File | Settings | File Templates.
 */
public class Interval {
	public static int interval(Work[] works) {
		Arrays.sort(works);
		int count = 0;
		//当前工作的结束时间
		int t = 0;
		for (int i = 0; i < works.length; i++) {
			if(t < works[i].getStart()) {
				count ++;
				t = works[i].getTerminate();
			}
		}
		return count;
	}

	public static void main(String args[]) {
		Work[] works = {
			new Work(1, 3),
			new Work(2, 5),
			new Work(4, 7),
			new Work(6, 9),
			new Work(8, 10)
		};
		int result = interval(works);
		System.out.println(result);
	}
}

class Work implements Comparable {
	private int start;
	private int terminate;

	Work(int start, int terminate) {
		this.start = start;
		this.terminate = terminate;
	}

	int getStart() {
		return start;
	}

	void setStart(int start) {
		this.start = start;
	}

	int getTerminate() {
		return terminate;
	}

	void setTerminate(int terminate) {
		this.terminate = terminate;
	}

	@Override
	public int compareTo(Object o) {
		Work work = (Work) o;
		if (this.terminate > work.getTerminate())
			return 1;
		else if (this.terminate == work.getTerminate())
			return 0;
		else
			return -1;
	}
}

 

算法复杂度:

    时间复杂度  On(nlogn) = 排序O(nlogn) + 扫描O(n)

本文转载自:http://blog.csdn.net/luoweifu/article/details/18195607

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
零基础学贪心算法

本文在写作过程中参考了大量资料,不能一一列举,还请见谅。 贪心算法的定义: 贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,只做出在某...

angel_kitty
2017/02/24
0
0
算法设计与分析复习——第四章:贪心算法

第四章:贪心算法 1,贪心算法的设计思想是什么,有什么特点?如果一个问题用贪心算法可以获得全局最优解,那么该问题的求解应满足哪些条件? 答:贪心算法的设计思想是在对问题求解时,总是...

科技小能手
2017/11/12
0
0
活动安排问题--贪心算法

  活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合,是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂...

青夜之衫
2017/12/05
0
0
【信息学奥赛一本通 提高组】第一章 贪心算法

一、贪心算法的特点: 1、贪心选择:   所谓贪心选择是指应用同一规则,将原问题变为一个相似的但规模更小的子问题,而后的每一步都是当前看似最佳的选择,且这种选择只依赖于已做出的选择...

Osea
07/09
0
0
程序员进阶之算法练习(三十)附基础教程

前言 BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 正文 1.k-th divisor 题目链接 题目大意...

落影loyinglin
2018/07/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

用 Sphinx 搭建博客时,如何自定义插件?

之前有不少同学看过我的个人博客(http://python-online.cn),也根据我写的教程完成了自己个人站点的搭建。 点此:使用 Python 30分钟 教你快速搭建一个博客 为防有的同学不清楚 Sphinx ,这...

王炳明
昨天
1
0
黑客之道-40本书籍助你快速入门黑客技术免费下载

场景 黑客是一个中文词语,皆源自英文hacker,随着灰鸽子的出现,灰鸽子成为了很多假借黑客名义控制他人电脑的黑客技术,于是出现了“骇客”与"黑客"分家。2012年电影频道节目中心出品的电影...

badaoliumang
昨天
10
0
很遗憾,没有一篇文章能讲清楚线程的生命周期!

(手机横屏看源码更方便) 注:java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期,但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

彤哥读源码
昨天
12
0
jquery--DOM操作基础

本文转载于:专业的前端网站➭jquery--DOM操作基础 元素的访问 元素属性操作 获取:attr(name);$("#my").attr("src"); 设置:attr(name,value);$("#myImg").attr("src","images/1.jpg"); ......

前端老手
昨天
6
0
Django的ChoiceField和MultipleChoiceField错误提示,选择一个有效的选项

在表单验证时提示错误:选择一个有效的选项 例如有这样一个表单: class ProductForm(Form): category = fields.MultipleChoiceField( widget=widgets.SelectMultiple(), ...

编程老陆
昨天
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部