Daily Hard (1)

leetcode 57.插入区间

题目描述：

给出一个无重叠的，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要，可以合并区间）。

**示例1： **

输入： intervals = [[1,3],[6,9]], newInterval = [2,5]

输出： [[1,5],[6,9]]

实例2：

输入： intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出： [[1,2],[3,10],[12,16]]
**解释： ** 新的区间[4,8] 与给出的区间集合中的区间有重合部分，取所有重合部分的并集合，得到最终无重合有序区间集合。

解题思路：

插入一个新的区间，需要考虑的是新的区间是否和现有的区间有重叠的部分，已知现有的区间集合中所有区间无交叉且有序，则

从头遍历区间数组，比较新区间的右端点与所有区间的左端点，来定位新区间的右边界；比较新区间的左端点与所有区间的右端点，定位新区间的左边界；

遍历时有如下判断：

• 创建一个存放区间的集合，进行区间的添加
• 如果新区间的左端点 > 当前遍历区间的右端点：
  • 加入当前区间，迭代下一个区间进行判断
• 如果新区间的右端点 < 当前遍历区间的左端点
  • 则要加入新区间，设定完成标识，迭代加入余下区间
• 都不满足时，新区间和现有区间有重叠，合并重叠的区间
  • 合并区间时左端点选择两个左端点中较小的一个
  • 合并区间时右端点选择两个右端点中较大的一个
  • 合并成一个区间后作为新区间去迭代完成遍历
• 如果遍历完成后，新区间仍然没有完成添加，则最终加入新区间

算法代码：

//执行用时：1 ms, 在所有 Java 提交中击败了99.48%的用户
//内存消耗：40.6 MB, 在所有 Java 提交中击败了92.52%的用户
public int[][] insert1(int[][] intervals, int[] newInterval) {
    if(newInterval.length == 0) return intervals;
    List<int[]> list = new ArrayList<>();
    int l = newInterval[0], r = newInterval[1];
    boolean flag = false;   //记录新集合是否已经添加进去，true的话后续不用比较
    for(int[] interval : intervals)&#123;
        if(interval[0] > r)&#123;
            if(!flag)&#123;
                list.add(new int[]&#123;l,r&#125;);
                flag = true;
            &#125;
            list.add(interval);
        &#125;
        else if(interval[1] < l)&#123;
            list.add(interval);
        &#125;else&#123;
            //此时，当前集合与新集合一定有交集的，合并称为一个集合作为新集合
            l = Math.min(l,interval[0]);
            r = Math.max(r,interval[1]);
        &#125;
    &#125;
    //如果遍历结束后新集合仍然没有加入，则最后加入
    if(!flag) list.add(new int[]&#123;l,r&#125;);

    //将list中的集合转到二维数组进行结果返回
    int[][] res = new int[list.size()][2];
    for(int i = 0; i < res.length; i++)&#123;
        res[i] = list.get(i);
    &#125;
    return res;        
&#125;