力扣解题思路：区间排序问题

435. 无重叠区间

思路：每次遇到和区间有关的题都要思考半天区间的排序方法，是根据区间左边排序还是根据区间右边排序呢？ 另外遇到这种题目如果采取贪心算法最后的结果会不会是最优的呢？（主要是因为研究生期间我的研究方向是强化学习算法，其中用到的贪婪算法容易陷入局部最优，所以每次看到适合用贪婪算法解题的题目时总会思考贪婪算法会得出最优解吗？）-> 首先，分析我们的目标是要找到找到需要移除区间的最小数量，所以想到贪心算法：先计算最多能组成的不重叠区间个数，然后用区间总个数减去不重叠区间的个数。此时就应该先排序，那么如何排序呢？-> 按区间的结尾进行升序排序，每次选择结尾最小，并且和前一个区间不重叠的区间。因此我们按照区间结尾来使用lambda表达式排序。

在每次选择中，选择的区间结尾越小，留给后面的区间的空间越大，那么后面能够选择的区间个数也就越大。自然这样贪心算法并不会到达局部最优，这就是按区间的结尾进行升序排序的根本原因。排序代码如下：

Arrays.sort(intervals,(o1,o2)->(o1[1]-o2[1]));

完整代码如下：

class Solution { public int eraseOverlapIntervals(int[][] intervals) { if(intervals.length == 0) return 0; Arrays.sort(intervals,(o1,o2)->(o1[1]-o2[1])); int end = intervals[0][1]; int count = 1; for(int i=1;i<intervals.length;i++){ if(intervals[i][0]>=end){ count++; end = intervals[i][1]; } } return intervals.length-count; } }

452. 用最少数量的箭引爆气球

同样的道理，如452. 用最少数量的箭引爆气球，使用的也是同样的思想，只不过此时边界重叠也必须算在作重叠区间，使用lambda表达式排序：

Arrays.sort(points,(o1,o2)->(o1[1]-o2[1]));

完整代码如下：

class Solution { public int findMinArrowShots(int[][] points) { if(points.length == 0) return 0; Arrays.sort(points,(o1,o2)->(o1[1]-o2[1])); int end = points[0][1]; int count = 1; for(int i=1;i<points.length;i++){ if(end<points[i][0]){ count++; end = points[i][1]; } } return count; } }

406. 根据身高重建队列

说到区间问题，还有406. 根据身高重建队列的解题方法也比较巧妙，一个学生用两个分量 (h, k) 描述，h 表示身高，k 表示排在前面的有 k 个学生的身高比他高或者和他一样高。也涉及到区间的排序-> 对于这种排队的题目，我们第一想法是 按照K升序排序,因为位于队列前方的人的前面的人数自然是较小的，但是这样是存在问题的，人数是符合要求了，但是k的含义弄错了，k不是前面排的人数，而是前面比他高的人数，所以先 按照K升序排序在逻辑上行不通。

那我们转换一下思想，我们按照采用h降序排序，遇到h相同的按照K升序排序（不可以按照降序，因为如果按照降序，插入的索引过大会导致该索引可能一开始就不存在），你以为这就结束了吗？这仍然是不对的，因为我们还需要对这个队列再次处理，现在开始真正的排队：

我们再对队列中的元素进行顺序插入操作，插入时按照k作为索引，我们一个一个地排队，对于前面已经排好的队，如果我们在k的位置插入一个新人，那么对k之前的人没有任何影响（因为插在其后面），对于k之后比新人高的人也没有任何影响（因为插入的人属于身高比较高而，k较小的，比如我们往同一个位置k插入了多次，那么后插入的一定是h较小的，就会把先插入在k位置的元素挤到后面去，但是因为后插入的元素h比先插入的小，所以不影响先插入k的元素的前面比他大元素的个数，也就是只要插入k位置的，前面比他大的元素永远都是只有k个，满足题目要求），因此，我们每插入一个人的时候，要么保证前面所有人都比新人高，要么至少保证插入的位置后面的所有人都比新人高，这就要求我们在排序的时候当身高相同时k递增排序。 我们还是使用lambda表达式对数组排序：

Arrays.sort(people,(a, b) -> (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));

因为链表的特新适合插入和删除节点，所以我们在链表上完成这个队列的插入操作：

class Solution { public int[][] reconstructQueue(int[][] people) { if (0 == people.length || 0 == people[0].length) return new int[0][0]; //按照身高降序 K升序排序 Arrays.sort(people,(a, b) -> (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0])); List<int[]> list = new ArrayList<>(); //K值定义为 排在h前面且身高大于或等于h的人数 //因为从身高降序开始插入，此时所有人身高都大于等于h //因此K值即为需要插入的位置 for (int[] i : people) { list.add(i[1], i); //add插入时，该位置及该位置之后的的数后移一个位置，这是关键 } return list.toArray(new int[list.size()][2]); } }

例如：

[7,0], [7,1], [6,1], [5,0], [5,2], [4,4] 再一个一个插入。 [7,0] [7,0], [7,1] [7,0], [6,1], [7,1] [5,0], [7,0], [6,1], [7,1] [5,0], [7,0], [5,2], [6,1], [7,1] [5,0], [7,0], [5,2], [6,1], [4,4], [7,1]

406. 根据身高重建队列

思路： 二分法我觉得实在没必要，因为要在排序的同时保存索引以便后续使用我们就得使用treeMap，因为treeMap天生根据key值排序，所以key就设置为我们需要排序的元素，而value自然就是索引。

因为我们要找到每个元素对应的右边区间，所以我们会根据此区间的右边界来寻找目标区间（目标区间即为左边界大于当前区间右边界的区间），因此treeMap有个ceiling方法刚好可以帮我们完成任务~~所以我们key中需要保存的是区间右边界！！

public int[] findRightInterval(Interval[] intervals) { TreeMap<Integer, Integer> starts = new TreeMap<>(); int res[] = new int[intervals.length]; for (int i = 0; i < intervals.length; i++) { starts.put(intervals[i].start, i); } for (int i = 0; i < intervals.length; i++) { Map.Entry<Integer, Integer> pos = starts.ceilingEntry(intervals[i].end); res[i] = pos == null ? -1 : pos.getValue(); } return res; }

986. 区间列表的交集

思路： 这一题，题目中的意思很明显，就是无需排序！！我们可以采用双指针的方式对比A和B的头指针指向的区间：

public int[][] intervalIntersection(int[][] A, int[][] B) { List<int[]>list=new ArrayList<>(); for(int i=0,j=0;i<A.length&&j<B.length;){ int left=Math.max(A[i][0],B[j][0]); int right=Math.min(A[i][1],B[j][1]); if(left<right){ list.add(new int[]{left,right}); }else if(left==right){ list.add(new int[]{left,left}); } if(A[i][1]<B[j][1]) i++; else j++; } return list.toArray(new int[list.size()][]); }

注意 list.toArray 可以直接将链表转成数组！！