给定n个任务接受同一台机器加工, 任务i有服务时间和要求截止时间(ti,di), 找出最小延迟方案，即所有任务延迟时间最大值的最小化问题。如3个任务 1、2、3，服务时间和截至时间为（2，4）（1，2）（ 7，7），如按照1-2-3顺序安排，各任务的延迟为0，1，3，延迟的最大值为3。 使用贪心算法，如下哪种贪心策略可得到最优解 ？
A: 以服务时间ti从小到大安排
B: 以di-ti从小到大安排
C: 以截止时间di从小到大安排
D: 以上都不可能
A: 以服务时间ti从小到大安排
B: 以di-ti从小到大安排
C: 以截止时间di从小到大安排
D: 以上都不可能
举一反三
- 【单选题】调度问题:有n个客户带来n项任务,每项加工时间已知,设为ti,i=1,2,...,n。从0时刻开始,陆续安排到一台机器上加工。每个任务的完成时间是从0时刻到该任务加工完成的时间。为了使尽可能多的客户满意,我们希望找到是的总等待时间最少的调度方案。该问题的贪心策略是() A. 加工时间长的优先安排 B. 加工时间短的优先安排 C. 完成时间早的优先安排 D. 等待时间长的优先安排
- 有三个作业A，B，C。它们的到达时间分别是0, 1, 3 ；要求服务时间分别是：4, 2, 1。若采用最高时间片轮转调度算法，时间片为2。作业A,作业B和作业C的完成时间是（ ） A: 4, 2, 6 B: 4， 6, 7 C: 6, 7, 4 D: 6, 4, 7
- 已知学校会议厅收到5个活动申请,它们的开始时间和结束时间如下表所示: 活动 活动1 活动2 活动3 活动4 活动5 开始 6 2 1 5 4 结束 10 6 3 7 8 若要使安排的活动数目最多,按照活动安排问题贪心算法得到的最大相容活动集合,下列哪个是错误的? 。 A: {3,4} B: {3,5} C: {3,1} D: {1,4}
- 注视时间应该占谈话时间的____？ A: 1/3 B: 2/3 C: 3/4 D: 2/1
- 有5件任务都需要两步操作（先1后2）来完成，下表给出了相应的加工时间。任务 操作1所需时间（小时) 操作2所需时间(小时)A 3.0 1.2B 2.0 2.5C 1.0 1.6D 3.0 3.0E 3.5 1.5[br][/br]根据Johnson算法安排工作顺序。