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

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

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;
    }
}

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;
    }
}

那我们转换一下思想，我们按照采用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]

思路：
二分法我觉得实在没必要，因为要在排序的同时保存索引以便后续使用我们就得使用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;
}

思路：
这一题，题目中的意思很明显，就是无需排序！！我们可以采用双指针的方式对比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 可以直接将链表转成数组！！