LeetCode第57题插入区间

继续打卡算法题，今天学习的是LeetCode第57题插入区间，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。

分析一波题目

上一题56题合并区间 已经学习了怎么判断重叠区间，怎么合并区间，本题就不难了。最简单的做法，我们可以把要插入的区间和原区间集合先添加到一个新的区间集合，然后排序，最后做一次合并，后面的流程和56题一样。

        int[][] newIntervals = new int[intervals.length+1][1];
        System.arraycopy(intervals, 0, newIntervals, 0, intervals.length);
        newIntervals[newIntervals.length-1] = newInterval;
        Arrays.sort(newIntervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));

通过上面的代码组成了新的区间集合，只要对newIntervals中重叠的区间进行合并，这个做法虽好理解，但是性能就降低了，因为题目已经说明原区间已经按左边界排序了,因此本题可以有更优的做法。

由于原区间集已经有序了，我们可以按如下步骤来执行插入操作。

1、将与要插入的区间无重叠的，加入到新的区间集

2、将与要插入的区间有重叠的，执行合并

3、将与要插入的区间无重叠的，加入到新的区间集

本题解题技巧

1、将原区间集分段，分为与新区间左边界偏离的一段，与新区间有重叠的，与新区间右边界偏离的一段

编码解决

重组区间集合，再排序解法

class Solution {

    public int[][] insert(int[][] intervals, int[] newInterval) {

        //存储结果

        LinkedList result = new LinkedList();

        //按左边界排序

        int[][] newIntervals = new int[intervals.length+1][1];

        //重组新区间集

        System.arraycopy(intervals, 0, newIntervals, 0, intervals.length);

        newIntervals[newIntervals.length-1] = newInterval;

        Arrays.sort(newIntervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));

        System.out.println(newIntervals.length);

        //第一个先加入结果

        result.add(newIntervals[0]);

        //从第二个开始判断是否重叠

        for (int i = 1; i < newIntervals.length; i++) {

            //和前面的重叠了

             System.out.println(i);

            System.out.println(newIntervals[i]);

            if (newIntervals[i][0]