406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

思路

先按照身高h来排序，身高一定是从大到小排（身高相同的话则k小的站前面），此时我们可以确定前面的节点身高一定都比本节点高！那么只需要按照身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。

例：排序完的people： [[7,0], [7,1], [6,1], [5,0], [5,2]，[4,4]]

插入的过程：

插入[7,0]：[[7,0]]
插入[7,1]：[[7,0],[7,1]]
插入[6,1]：[[7,0],[6,1],[7,1]]
插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

var reconstructQueue = function(people) {
    let res = [];
    // 排序
    people.sort((a, b) => {
        if(a[0] !==  b[0]) 
            return b[0] - a[0];
        else 
            return a[1] - b[1];
    })
    // 按k插入
    for (let i = 0; i < people.length; i++) {
        res.splice(people[i][1], 0, people[i])
    }
    return res;
};

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

思路

本题采用贪心，贪心策略为：局部若两集合相交，则两集合合并后的集合右边界是两集合中更大的右边界，左边界是更小的，这样就可以尽可能地排除掉重合的集合且覆盖输入中所有集合。

如何判断集合是否重叠

首先应该先按左边界从小到大的排序，这样两左边界相近的集合就在一起，再遍历集合，判断当前集合的左边界是否小于上一个集合的右边界，若小于则两边界有重叠，若大于则无重叠，则采用贪心策略更改当前集合的左右边界。当两集合没有重叠时就应该将上一个集合集合放入结果数组。

注意当集合遍历结束后，由于没有遇到无重叠情况，所以需要单独处理最后一个集合。

var merge = function(intervals) {
    // 左边界排序
    intervals.sort((a, b) => {
        return a[0] - b[0];
    })
    const res = [];
    // 遍历集合
    for (let i = 1; i < intervals.length; i++) {
        // 有重叠
        if (intervals[i][0] <= intervals[i - 1][1]) {
            intervals[i][1] = Math.max(intervals[i][1], intervals[i - 1][1]);
            intervals[i][0] = Math.min(intervals[i][0], intervals[i - 1][0]);
        } else {//无重叠
            res.push(intervals[i - 1]);
        }
    }
    // 处理最后一个集合
    res.push(intervals[intervals.length - 1]);
    return res;
};

435. 无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

思路

本题还是采用贪心方法，贪心策略：若两结合有重叠，则去除范围更大的集合，因为范围更大的集合更有可能与别的集合重叠，优先去除它就能有效的减少移除次数。

两步：

先按集合左边界进行从小到大排序
遍历集合，判断当前集合与前一个集合是否有重叠，若有则将当前集合的右边界改为两集合中更小的右边界（这一步相当于移出范围更大集合了），为下一次比较做准备。

为什么不更改左边界呢？

因为集合按左边界从小到大排序，所以当前集合左边界本就大于前一个集合的左边界，所以不需要更改。

var eraseOverlapIntervals = function(intervals) {
    // 左边界排序
    intervals.sort((a, b) => {
        return a[0] - b [0];
    })
    let count = 0;
    // 更改当前集合的右边界
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < intervals[i - 1][1] ) {
            intervals[i][1] =  Math.min(intervals[i][1], intervals[i - 1][1]);
             count++;
        }
    }
    return count;
};