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

2015/01/10 13:56
阅读数 1.2K

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

 

问题主题:区间调度问题

问题描述:

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)

展开阅读全文
打赏
0
1 收藏
分享
加载中
更多评论
打赏
0 评论
1 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部