乐趣区

关于程序员:贪心

区间贪婪

两个典型的问题:
区间不相交问题:给出 N 个开区间 (x,y),从中抉择尽可能多的开区间,使得这些开区间两两没有交加。
区间选点问题:给出 N 个闭区间 [x,y],求起码须要确定多少个点,能力使每个闭区间中都至多存在一个点。
策略:先将区间依照左端点从大到小排序,左端点雷同则依照右端点从小到大排序。而后顺次抉择不与上一个区间相交的最左边的区间即可。
原理:对于排序后的区间 a 和 b(a 的左端点在 b 的左端点的左边),有两种状况:a 蕴含于 b,a 不蕴含于 b。对于第一种状况必然选择 a,因为这样左右两边都更节俭空间来搁置更多的区间。而对于第二种状况,则仍然抉择 a,因为 a 右端点比 b 右端点多出的局部已无奈利用,不予考虑,而相较于 b,a 左端点少占用了空间,故必然选择 a。(能够本人画图了解)
留神,因为所给区间的开闭以及事实的意义不同,在取下一个区间时,灵便判断所取区间端点是否能够重合。

退出移动版