一个区间问题的变种,求贪心算法
给定一个24小时区间的集合,尽可能地选择更多的区间(区间之间不能重叠)
然后跟一般的区间问题不同的是,每个区间都可以跨过0时,也就是说10pm-2am是可能的
譬如说给定如下的区间集合:
6pm-6am
9pm-4am
3am-2pm
1pm-7pm
最优解是选择9pm-4am,1pm-7pm
求贪心算法
[解决办法]
思路如下:
可以肯定的是,最优解必然包含至少一个区间。
假设有n个区间,我们进行n次迭代,其中第k次必然选择第k个区间,并将与之重叠的区间去掉,这样得到的必然是{第k个区间,不和第k个区间重叠的区间}这样一个集合。
因此我们可以以第k个区间为参照物,将所有区间平移t个单位使得k区间的开始时间为0,因为没有区间与k重叠,所以就不存在“过夜”的区间,然后就能够以完成时间为标准进行贪心算法了,这样得到的是以选择k区间为前提的,所以要进行n次迭代,以求出最大值。n次迭代×贪心算法O(n)=O(n^2)