[leetCode]57. 插入区间

一次遍历

这题的关键是判断两个区间是否存在交集,比如区间$S_1[l_1,r_1],S_2[l_2, r_2];如果r_1<l_2说明S_1在S_2左侧无交集，如果l_1>r_2则说明S_1>S_2则S_1在S_2右侧无交集，如果不符合以上两个条件则说明有交集，$则可以通过$[max(l_1,l_2),min(r_1,r_2)]$求交集，通过$[min(l_1,l_2),max(r_1,r_2)]$求并集。
通过遍历区间数组如果当前区间与新区间S无交集则直接加入答案，如果有交集则与新区间S进行合并，如果第一次遇到在S右侧（$l>left$）的区间则将S加入答案，然后加入当前区间，遍历完数组后如果不存在这样的区间则需要把S加入答案。

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        // newInterval 区间的左右下标
        int left = newInterval[0];
        int right = newInterval[1];
        // 存放答案的列表
        List<int[]> ans = new ArrayList<>();
        // bool 变量 判断是否加入S
        boolean placed = false;
        // 遍历原来的区间数组
        for (int[] interval : intervals) {
            // 在插入区间右侧无交集
            if (interval[0] > right) {
                // 如果没有加入S
                if (!placed) {
                    ans.add(new int[]{left, right});
                    placed = true;
                }
                ans.add(interval);
            } else if (interval[1] < left) {
                // 在插入区间左侧且无交集
                ans.add(interval);
            } else {
                // 与插入区间有交集 计算并集
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        // 如果不存在这样的区间则将s加入答案
        if (!placed) {
            ans.add(new int[]{left, right});
        }
        int[][] fans = new int[ans.size()][2];
        for (int i = 0; i < ans.size(); i++) {
            fans[i] = ans.get(i);
        }
        return fans;
    }
}