贪心算法之区间问题详解

目录
1.贪心算法简介
基本思想
局限性
2.经典例题
区间问题
贪心策略
3.代码
__
1.贪心算法简介
基本思想
1）贪婪算法（贪心算法）是指在对问题进行求解时，在每一步选择中都采取最好或者最优（即最有利）的选择，从而希望能够导致结果是最好或者最优的算法。
2）贪婪算法所得到的结果不一定是最优的结果（有时候会是最优解），但是都是相对近似（接近）最优解的结果。
局限性
贪心算法失效的很大一个原因在于它明显的局限性：它几乎只考虑局部最优解。 所谓局部最优，就是只考虑当前的最大利益，既不向前多看一步，也不向后多看一步，导致每次都只用当前阶段的最优解。 因此在绝大多数情况下，贪心算法不能得到整体最优解，但它的解是最优解的一个很好近似。
2.经典例题
区间问题
给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。
输入输出样例
__
输入是一个数组，数组由多个长度固定为2的数组组成，表示区间的开始和结尾。
输出一个整数，表示需要移除的区间数量。
__
Input :[1,2],[2,4],[1,3]]
__
Output :1
在这个样例中，我们可以移除区间［1,3]，使得剩余的区间［1,2],[2,4]]互不重叠。
贪心策略
在选择要保留区间时，区间的结尾很重要：选择的区间结尾越小，余留给其它区间的空间
就越大，就越能保留更多的区间。
因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。具体实现方法为：
1.先把区间按照结尾的大小进行增序排序，
2.每次选择结尾最小且和前一个选择的区间不重叠的区间。
在样例中，排序后的数组为［1,2],[1,3],[2,4]]。按照我们的贪心策略，首先初始化为区间[1,2]；由于［1,3］与［1,2］相交，我们跳过该区间；由于［2,4］与［1,2］不相交，我们将其保留。因此最终保留的区间为［1,2],[2,4]。
3.代码

1. import java.util.Arrays;
2. import java.util.Comparator;
4. public class Solution {
5. public static int merge(int[][] intervals) {
6. //先按照区间结尾的大小进行升序排序
7. Arrays.sort(intervals, new Comparator<int[]>() {
8. @Override
9. public int compare(int[] o1, int[] o2) {
10. return o1[1] - o2[1];
11. }
12. });
13. int count =1;//区间不重合的个数，默认第一个满足题意，初始化为1
14. int cur = intervals0;//排序完成后贪心选择的最小的区间结尾
15. for (int i = 1; i < intervals.length; i++) {
16. if(intervalsi >= cur) {
17. count++;
18. cur=intervalsi;
19. }
20. }
21. //所有区间的个数减去不重叠区间的个数，就是重叠区间的个数。
22. return intervals.length - count;
23. }
24. }