Question

求高手！解一道算法设计综合题目！!内容如下

现有n个任务{1，2，……n}和m台机器，每个任务i占用的起止时间为[si,fi](si秒为开始加工，fi秒结束)，m台机器均可以处理每个任务。所谓可行的任务分配时指在分配中没有不相容的任务分配到同一台机器上。如何分配才能使得所有机器最少（设计一种算法，详细写出求解步骤，分析算法复杂度，给出伪代码过程） 谢谢！

Answer 1

最少机器数，即将所有任务按时间序排列后，同一时间段（或同一时间点）内最大的并行任务数。
这一题可以用贪心的算法来求解。

求解步骤：
依次读入每个任务的起止时间；
使用某一数据结构对已读入的任务涵盖的时间段内的并行任务数进行记录；
全部数据读入完成后，从存储的数据中找出并行数的最大值即题目的解。

算法的时间复杂度和空间复杂度取决于存储结构，下面举两例分析，设任务起止时间为[0，S]。
1.使用一线性表存储每秒并行数，其时间复杂度为O(n*S)，空间复杂度为O(S)；
2.使用线段树存储每段时间的并行数，其时间复杂度为O(n*log2S)，空间复杂度为O(S)。有关线段树的介绍可以参考网上的介绍，这里不详细解释了。

伪代码过程：
init store; //初始化存储，将全段时间的并行数设为0
loop i from 1 to n
read(si, fi); //读入n组时间
store[si, fi] + 1; //在存储结构中标记si到fi区间内的并行数加1

end while;
loop s from min_si to max_fi
max_m = max(store[s], max_m); //遍历全段时间，得到最大并行数
print max_m; //输出结果

追问

谢谢，但是伪代码 能写成c++语言不？

追答

int store[MAX_S];
memset(store, 0, sizeof(int)*MAX_S);

for(int i = 0; i < n; ++i)
{
int si = readint();
int fi = readint();
for(int j = si; j <=fi; ++j)
{
++store[j];
}
}

for(int i = 0; i < MAX_S; ++i)
{
max_m = max(store[i], max_m);
}

print (max_m);

这个是伪代码，旨在描述算法的执行过程，如果需要编译运行，有些地方要做适当的修改。

追问

有些地方写错了，给我一个完整，能运行的程序吧

追答

#include
#include
#define MAX_S 1001
void main()
{
int store[MAX_S], i, j, n, max_m = 0, si, fi;
memset(store, 0, sizeof(int)*MAX_S);
scanf("%d", &n);
for(i = 0; i max_m ? store[i] : max_m;
}
printf("m:%d\n", max_m);
sleep(10);
}
遇到问题最好先自己想办法解决，看别人写的程序和自己写完全是两码事

Answer 2

应该是所用时间最少吧，要想让机器最少，只用一台就好了?
基本思路：
//用一个vector容器存储任务时间信息
typedef tuple<int,int> Task;
vector<Task> Schedule[100];
//之后对时间循环，当检测到有任务开始或结束时，更改相应的当前使用机器数量。
while(TaskLeft != 0){
if(TaskNew())++Machine,--TaskLeft;
assert(Machine <= m); //若检测到当前机器数大于m，则说明任务并行不可实现
else if(TaskOver())--Machine;
}