57. 插入区间

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        LinkedList<int[]> res = new LinkedList<>();
        boolean hasIn = false;
        for (int[] interval : intervals) {
            if (interval[0] > newInterval[1]) {
                // 没有交集，当前区间在新区间的右边
                if (!hasIn) {
                    // 如果新区间还没有加入进去，则先把新区间加入结果集
                    res.add(newInterval);
                    hasIn = true;
                }
                res.add(interval);
            } else if (interval[1] < newInterval[0]) {
                // 没有交集，当前区间在新区间的左边，则直接加入
                res.add(interval);
            } else {
                // 存在交集，则需要更新新的区间
                // 但要注意：不需要把当前区间加入结果集
                newInterval[0] = Math.min(newInterval[0], interval[0]);
                newInterval[1] = Math.max(newInterval[1], interval[1]);
            }
        }
        if (!hasIn) {
            res.add(newInterval);
        }
        return res.toArray(new int[res.size()][2]);
    }
}

• 时间复杂度 O(n)
• 空间复杂度 O(n)