区间调度问题 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 有n项工作, 每项工作分别在s时间开始, 在t时间结束. 对于每项工作可以选择参与与否, 如果参与, 则全程参与.

参与时间段不能重叠, 包括起始结束瞬间也不能重叠. 求最多能参与多少项工作?

使用贪心法, 策略是在可选工作中, 每次都选取结束时间最早的工作.

代码:

/*
 * main.cpp
 *
 *  Created on: 2014.7.17
 *      Author: spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include <stdio.h>
#include <limits.h>

#include <utility>
#include <queue>
#include <algorithm>

using namespace std;

class Program {
	static const int MAX_N = 10000;
	int N=5, S[MAX_N]={1,2,4,6,8}, T[MAX_N]={3,5,7,9,10};
	pair<int, int> itv[MAX_N];

public:
	void solve() {
		for (int i=0; i<N; i++) {
			itv[i].first = T[i]; //结束时间在前, 可以排序.
			itv[i].second = S[i];
		}
		sort(itv, itv+N);
		int ans = 0, t = 0;
		for (int i=0; i<N; ++i) {
			if (t<itv[i].second) { //首尾不能重合
				ans++;
				t = itv[i].first;
			}
		}
		printf("result = %d\n", ans);
	}
};


int main(void)
{
	Program P;
	P.solve();
    return 0;
}

输出:

result = 3