[LeetCode] 57. Insert Interval

https://leetcode.com/

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the i^th 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 starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

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

 

Constraints:

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^5
• intervals is sorted by starti in ascending order.
• newInterval.length == 2
• 0 <= start <= end <= 10^5

 

 

Code :

var insert = function(intervals, newInterval) {
    // 결과를 저장할 배열
    const result = [];
    // 새로운 구간이 시작하는 지점까지의 구간을 결과에 추가
    let i = 0;
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        result.push(intervals[i]);
        i++;
    }
    // 겹치는 구간을 병합
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        // 새로운 구간과 현재 구간을 병합
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    // 병합된 새로운 구간을 결과에 추가
    result.push(newInterval);
    // 나머지 구간을 결과에 추가
    while (i < intervals.length) {
        result.push(intervals[i]);
        i++;
    }
    // 최종 결과 반환
    return result;
};

 

Solutions Code :

var insert = function (intervals, newInterval) {
  // 새로운 구간의 시작과 끝을 각각 변수에 할당
  let [start, end] = newInterval;
  // 시작점이 새로운 구간보다 작은 구간을 저장할 배열
  let left = [];
  // 끝점이 새로운 구간보다 큰 구간을 저장할 배열
  let right = [];
  // 기존 구간 배열을 순회
  for (const interval of intervals) {
    // 현재 구간의 시작과 끝을 변수에 할당
    const [first, last] = interval;
    // 현재 구간의 끝이 새로운 구간의 시작보다 작으면 왼쪽에 추가
    if (last < start) left.push(interval);
    // 현재 구간의 시작이 새로운 구간의 끝보다 크면 오른쪽에 추가
    else if (first > end) right.push(interval);
    // 겹치는 경우, 새로운 구간을 확장
    else {
      start = Math.min(start, first);
      end = Math.max(end, last);
    }
  }
  // 왼쪽 + 병합된 새로운 구간 + 오른쪽 순서로 반환
  return [...left, [start, end], ...right]; 
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode