贪心-任务调度问题_任务调度 贪心

问题描述：

假设给定n个任务的集合T，每个任务i有启动时间si和完成时间fi(si<fi)。任务i必须在si时刻启动，并在fi时刻结束。每个任务都必须在一台机器上执行，每台机器同时只能执行一个任务。如果两个任务i和j的实行时间不重叠，即fi<= sj或fi<=si，则称这两个任务不冲突。显然，只有两个任务不冲突时才可以安排它们在同一台机器上执行。
如何安排T中所有任务在不冲突的条件下在最少的机器上完成？

问题分析：

要求： 在最少的机器上安排完所有任务。
如何选择贪心策略才能使问题的解为最优解？显然，开始时间最早的任务需要被先执行，但是最优解要求我们使用的机器最少，因此我们每次选择时应尽量使用相同的机器。若已使用过的机器上现处于空闲状态，则应将待执行任务放到该机器上执行。若无空闲机器，则再使用新机器。

代码示例O(n^2)：

#include<iostream>
#include<algorithm>
using namespace std;

struct thread{
 	int s;
 	int e;
}trd[1001];

bool cmp(thread x, thread y){
 	return x.s < y.s;
}

int main(){
 	int n;
	cin >> n;
 	int k[n], ki = 0, rcd[n];
 	for(int i = 0; i < n; i++){
  		cin >> trd[i].s >> trd[i].e;
 	}
 	sort(trd, trd+n, cmp);
 	k[ki++] = trd[0].e;
 	rcd[0] = ki;
 	for(int i = 1, t = -1; i < n; i++){
  		for(int j = 0; j < ki; j++){
   			if(k[j] <= trd[i].s){
    				t = j;
    				break;
   			}
  		}
  		if(t != -1){
   			k[t] = trd[i].e;
   			rcd[i] = t+1;
  		} else {
   			k[ki++] = trd[i].e;
   			rcd[i] = ki;
  		}
 	}
 	for(int i = 0; i < n; i++){//输出各任务在哪台机器上运行
  		cout << rcd[i] << " ";
 	}
 	cout << "\n" << ki;
 	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

最优解证明：

设在上述策略下最后一台选择的机器为第k台，i为第一个在k上运行的任务。则1到k-1台机器上都有任务正在运行，即i与前1到k-1个任务相冲突，并且1到k-1台机器上运行的任务之间也是相互冲突的。因此任务集合T中至少有k个任务之间相互冲突，若使用k-1台机器，则无法同时安排它们执行，因此最少使用k台机器。

参考文献《算法设计与应用》