神马作文网解一道算法设计综合题目!内容如下
来源：学生作业帮 编辑：神马作文网作业帮 分类：数学作业 时间：2024/11/20 03:12:17
解一道算法设计综合题目!内容如下
现有n个任务{1,2,……n}和m台机器,每个任务i占用的起止时间为[si,fi](si秒为开始加工,fi秒结束),m台机器均可以处理每个任务.所谓可行的任务分配时指在分配中没有不相容的任务分配到同一台机器上.如何分配才能使得所有机器最少（设计一种算法,分析算法复杂度,给出伪代码过程）
现有n个任务{1,2,……n}和m台机器,每个任务i占用的起止时间为[si,fi](si秒为开始加工,fi秒结束),m台机器均可以处理每个任务.所谓可行的任务分配时指在分配中没有不相容的任务分配到同一台机器上.如何分配才能使得所有机器最少（设计一种算法,分析算法复杂度,给出伪代码过程）
最少机器数,即将所有任务按时间序排列后,同一时间段（或同一时间点）内最大的并行任务数.
这一题可以用贪心的算法来求解.
依次读入每个任务的起止时间；
使用某一数据结构对已读入的任务涵盖的时间段内的并行任务数进行记录；
全部数据读入完成后,从存储的数据中找出并行数的最大值即题目的解.
算法的时间复杂度和空间复杂度取决于存储结构,下面举两例分析,设任务起止时间为[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
这一题可以用贪心的算法来求解.
依次读入每个任务的起止时间；
使用某一数据结构对已读入的任务涵盖的时间段内的并行任务数进行记录；
全部数据读入完成后,从存储的数据中找出并行数的最大值即题目的解.
算法的时间复杂度和空间复杂度取决于存储结构,下面举两例分析,设任务起止时间为[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