贪心算法
顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
-
该算法存在问题：
①不能保证求得的最后解是最佳的；
②不能用来求最大或最小解问题；
③ 只能求满足某些约束条件的可行解的范围。
区间贪心
- 区间贪心的问题描述
给出N个开区间（x，y）,从中选择尽可能多的开区间，使得这些区间两两没有交集。
考虑：
- （1）区间相交
- （2）区间不相交
- （3）区间包含（特殊的区间相交）
2.解决的办法 - （1）当区间包含时，我们只留小区间。
- （2）然后我们将所有区间的左端点也就是 x 从大到小排序，然后每次找出右端点在这个左端点左面的就是一个，然后选取这个区间的左端点作为下次判断的标准，当左端点相同时，按照右端点 y 从小到大排序，就是我们检查时先检查（左端点相同时）右端点小的（正好可以去去除区间包含的大区间）
-
首先明确一个问题：假设有两个区间x,y，区间x完全包含y。那么，选x是不划算的，因 为x和y最多只能选一个，选x还不如选y，这样不仅区间数目不会减少，而且给其他区间留出 了更多的位置。接下来，按照bi从小到大的顺序给区间排序。
贪心策略是：一定要选第一个 区间。
图1 - 来看图1中的区间1和区间2：
如果区间2和区间1完全 不相交，那么没有影响（因此一定要选区间1），否则区间1和区间2最多只能选一个。如果 不选区间2，区间1的①部分其实是没有任何影响的（它不会挡住任何一个区间），区间1的有效部 分其实变成了②部分，它被区间2所包含！由刚才的结论，区间2是不能选的。依此类推， 不能因为选任何区间而放弃区间1，因此选择区间1是明智的。
选择了区间1以后，需要把所有和区间1相交的区间排除在外，需要记录上一个被选择的 区间编号。这样，在排序后只需要扫描一次即可完成贪心过程，得到正确结果。
参考：
