贪心算法——间隔任务规划——python
2020-12-13 05:00
标签：main pre 开始 间隔 贪心 div als 时间 证明 间隔任务规划 问题描述 • 输?为 n 个报告集 R=[r1, …… , rn]，以及每?个报 告的开始不结束时间 ri=[ai, bi] • 输出：最多的相容报告集 • 两个报告相容：即两报告的发?时间??没有重合 贪心策略 每次选择结束时间最早的报告 输出结果 [[‘a‘, 1, 3], [‘c‘, 4, 7], [‘e‘, 8, 10]] 贪心算法需要证明结果是否正确 贪心算法——间隔任务规划——python 标签：main pre 开始 间隔 贪心 div als 时间 证明 原文地址：https://www.cnblogs.com/tangxinghe/p/11128168.htmldef get_max_intervalschedule(joblist):
job_schedule = []
num_job = len(joblist)
joblist.sort(key = lambda x: x[2]) #按照结束时间进行排序
for n in range(num_job):
if not len(job_schedule):
job_schedule.append(joblist[n])
else:
#job(n)是否与job_schedule中的jobs相容
if job_schedule[-1][2] ]:
#如果job_schedule中最后一个任务的结束时间小于joblist的开始时间
job_schedule.append(joblist[n])
return job_schedule
if __name__ == "__main__":
joblist = [["e", 8, 10], ["b", 2, 5],
["c", 4, 7],["a", 1, 3],
["d", 6, 9]
]
print(get_max_intervalschedule(joblist
下一篇：树状数组板子