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

问题主题：区间调度问题

问题描述：

有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)

#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<int, int> 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;

}

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