[PS] Leet | 57. 구간 삽입

문제

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

 

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

 

Return intervals after the insertion.

 

Note that you don't need to modify intervals in-place. You can make a new array and return it.

예시

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].

조건

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 105
• intervals is sorted by starti in ascending order.
• newInterval.length == 2
• 0 <= start <= end <= 105

답

interval의 위치는 두 가지 경우로 나눌 수 있습니다.

 

1. interval이 newInterval의 오른쪽 또는 왼쪽에 있을 때

2. interval과 newInterval이 겹쳐져 있을 때

 

그리고 newInterval의 위치도 두 가지 경우로 나눕니다.

 

3. intervals의 우끝단 또는 좌끝단에 있을 때

4. itnervals의 사이에 겹치는 구간 없이 있을 때

 

1번과 2번은 리스트를 순회하면서 확인합니다. 3번은 순회 시작 전과 순회 후 한 번씩 확인합니다. 4번의 경우 1번을 확인할 때 해당 interval 바로 다음에 newInterval이 오는지 확인합니다.

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function(intervals, newInterval) {
    const len = intervals.length;
    const res = [];
    const merged = [...newInterval];

    if (intervals.length == 0) {
        return [[...newInterval]];
    }

    if (newInterval[1] < intervals[0][0]) {
        res.push([...newInterval]);
    }

    for (let i=0; i<len; ++i) {
        const interval = intervals[i];

        if (interval[1] < newInterval[0] || newInterval[1] < interval[0]){
            res.push([...interval]);
            if (i<len-1 && interval[1] < newInterval[0] && newInterval[0] < intervals[i+1][0]) {
                res.push(merged);
            }
        } else {
            merged[0] = Math.min(interval[0], merged[0]);
            merged[1] = Math.max(interval[1], merged[1]);
            
            const resLen = res.length;
            if (resLen === 0 || res[resLen-1][0] !== merged[0] && res[resLen-1][1] !== merged[1]){
                res.push(merged);
            }
        }
    }

    if (newInterval[0] > intervals[len-1][1]) {
        res.push([...newInterval]);
    }

    return res;
};

시간복잡도 : O(n)

공간복잡도 : O(1)