解一道算法设计综合题目!内容如下
现有n个任务{1,2,……n}和m台机器,每个任务i占用的起止时间为[si,fi](si秒为开始加工,fi秒结束),m台机器均可以处理每个任务.所谓可行的任务分配时指在分配中没有不相容的任务分配到同一台机器上.如何分配才能使得所有机器最少(设计一种算法,分析算法复杂度,给出伪代码过程)
人气:427 ℃ 时间:2020-07-08 17:41:38
解答
最少机器数,即将所有任务按时间序排列后,同一时间段(或同一时间点)内最大的并行任务数.这一题可以用贪心的算法来求解.依次读入每个任务的起止时间;使用某一数据结构对已读入的任务涵盖的时间段内的并行任务数进行...谢谢,但是伪代码 能写成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 1001void 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 < n; ++i){scanf("%d %d", &si, &fi);for(j = si; j <=fi; ++j){++store[j];}}for(i = 0; i < MAX_S; ++i){max_m = store[i] > max_m ? store[i] : max_m;}printf("m:%d\n", max_m);sleep(10);}遇到问题最好先自己想办法解决,看别人写的程序和自己写完全是两码事
推荐
猜你喜欢