关于时间安排贪心算法正确性的证实

2021年09月15日 阅读数:1
这篇文章主要向大家介绍关于时间安排贪心算法正确性的证实,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

咱们令ai表示一个时间区间,具备两个属性si,ei表示开始和结束时间.ide

如今给定一个a的集合Sk,从Sk中找出一个最大兼容子集,即找出尽可能多的时间区间且这些区间互不相交。排序

之前只是知道按照结束时间排序而后直接贪心便可,没想过证实,昨晚看了黑书的证实。it

首先咱们假设这么一个定理:令am是Sk中e最小的区间,则am在SK的某一个最大兼容子集中class

证实:假设Ak为Sk的一个最大兼容子集,对于Ak具备的结束时间最先的区间设为aj,集合

则aj有两种状况:1.aj==am,与结论相符。兼容

                             2.aj!=am,因为am是Sk中结束时间最先的,因此显然em<=ej,又在Ak这个最大兼容集中的元素互不相交,因此咱们用am替换aj以后显然Ak仍是一个最大兼容子集!di

证毕。时间

上一篇: NYOJ 720 DP+二分
下一篇: vijos 1082