多做题,通过考试没问题!

算法设计与分析

睦霖题库>大学试题(计算机科学)>算法设计与分析

某体育馆有一羽毛球场出租,现在总共有10位客户申请租用此羽毛球场,每个客户所租用的时间单元如下表所示,s(i)表示开始租用时刻,f(i)表示结束租用时刻,10个客户的申请如下表所示: 同一时刻,该羽毛球场只能租借给一位客户,请设计一个租用安排方案,在这10位客户里面,使得体育馆能尽可能满足多位客户的需求,并算出针对上表的10个客户申请,最多可以安排几位客户申请。

正确答案: 将这10位客户的申请按照结束时间f(i)递增排序,如下表:

1、选择申请1(1,4)
2、依次检查后续客户申请,只要与已选择的申请相容不冲突,则选择该申请。直到所有申请检查完毕。申请4(5,7)、申请8(8,11)、申请10(11,13)
3、最后,可以满足:申请1(1,4)、申请4(5,7)、申请8(8,11)、申请10(11,13)共4个客户申请。这已经是可以满足的最大客户人数。
答案解析:
进入题库查看解析

微信扫一扫手机做题