试题详情
简答题 某体育馆有一羽毛球场出租，现在总共有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个客户申请。这已经是可以满足的最大客户人数。

  • 关注下方微信公众号，在线模考后查看

热门试题