计算机科学
首页
学历类考试
大学
计算机科学
简答题
某体育馆有一羽毛球场出租,现在总共有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个客户申请。这已经是可以满足的最大客户人数。
答案解析
略
分享
语音搜题
拍照搜题
打赏