[LeetCode] 57. Insert Interval

Posted on | In

Problem

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:

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

Example 2:

1
2
3
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].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Explanation

  1. We need to draw a picture to illustrate this problem.

    1
    2
    3
    4
       original interval: - - - - - -      - - - - -           - - - - -             - - - - - -
   added interval:                           - - - - - - - - - - - - - - -

   result:            - - - - - -      - - - - - - - - - - — - - - - - - -       - - - - - - -

  2. Iterate the original interval, if the interval’s end is greater than the added interval’s start, then they can merge, and we choose the smallest starting point between these two as the merge interval’s starting point. Then keep iterating, until the current interval’s start is greater than the added interval’s end, then we compare the previous interval with the added interval’s ending point and choose the greater ending point as the merge interval’s ending point.

    1
    2
    3
    4
     original interval: - - - - - -   - - - - -                   - - - - -            - - - - -
 added interval:                                 - - - -

 result:            - - - - - -    - - - - -     - - - -      — - - - -             - - - - -

  3. In the above case, step2’s method also apply.

    1
    2
    3
    4
     original interval:               - - - - -            - - - - -
 added interval:     - - - -

 result:             - - - -      - - - - -             — - - - -

  4. In the above case, we can initialize the merge inteval’s starting point and ending point as the added interval’s start and ending point.

    1
    2
    3
    4
     original interval:  - - - - -            - - - -
 added interval:                                        - - - - -

 result:             - - - - -            - - - -       - - - - -

  5. In the above case, after iterate to the last interval and we haven’t find the merge interval, we can just added the added interval to the result and return the result.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        int n = intervals.length;
        int i = 0;
        int nStart = newInterval[0];
        int nEnd = newInterval[1];
        
        while (i < n && intervals[i][1] < nStart) {
            res.add(intervals[i]);
            i += 1;
        }

        if (i == n) {
            res.add(newInterval);
            return res.toArray(new int[0][]);
        }

        nStart = Math.min(intervals[i][0], newInterval[0]);
        while (i < n  && intervals[i][0] <= newInterval[1]) {
            nEnd = Math.max(intervals[i][1], newInterval[1]);
            i += 1;
        }
        res.add(new int[]{nStart, nEnd});

        while (i < n) {
            res.add(intervals[i++]);
        }

        return res.toArray(new int[0][]);
    }
}