题目描述

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

算法

(实现题) O(n)

Java 代码

class Solution {

    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals == null || intervals.length == 0) {
            return new int[][] {newInterval};
        }

        int m = intervals.length;
        List<int[]> res = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            // 规定newInterval[1]只有在 < intervals[i][0]才插入res
            if (newInterval == null || intervals[i][1] < newInterval[0]) {
                res.add(intervals[i]);
            } else if (intervals[i][0] > newInterval[1]) {
                res.add(newInterval);
                newInterval = null;
                res.add(intervals[i]);
            } else {
                // 说明newInterval和intervals[i]两侧的其中一侧有交集
                newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
                newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            }
        }

        if (newInterval == null) {
            return res.toArray(new int[res.size()][2]);
        }

        // 注意这里, newInterval != null,说明newInterval大于所有intervals
        res.add(newInterval);
        return res.toArray(new int[res.size()][2]);
    }
}