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