56. Merge Intervals

💡 풀이

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  let arr = [];
  let prev = intervals[0];
  arr[0] = prev;

  for (let i = 0; i < intervals.length; i++) {
    let cur = intervals[i];

    if (cur[0] <= prev[1]) {
      prev[1] = Math.max(prev[1], cur[1]);
    } else {
      arr.push(cur);
      prev = cur;
    }
  }
  //console.log('arr: ', arr);
  return arr;
};

let intervals = [
  [2, 6],
  [1, 5],
  [9, 18],
  [19, 25],
];

merge(intervals);

📝 정리

유사 문제: https://velog.io/@ken1204/435.-Non-overlapping-Intervals

이전에 풀었던 유사한 문제가 생각나서 어렵지 않게 풀 거라고 생각했지만, 조금 시간이 걸린 문제였다. return 할 때, 공간복잡도를 O(1)으로 할 수 있는 방법이 있을까 하고 생각했지만.. 결국 생각을 못해서 새로운 배열 arr를 만들었다.

• 먼저, 시작점(intervals[i][0])을 기준으로 정렬 intervals 배열을 다시 정렬한다.

• 이후 prev(이전 intervals 배열의 요소)와 cur(현재 intervals 배열의 요소)이라는 변수를 만들어서, prev의 끝점(=prev[1])과 cur의 시작점(=cur[1])을 비교해서, 만약 prev의 끝점이 더 크다면, 그 구간은 겹친다는 의미이기에 merge를 진행해야 한다.

만약 겹치지 않는다면 해당 요소를 그대로 답이 되는 arr 배열에 push 해주고, prev는 cur로 업데이트 해준다.

수정, 지적을 환영합니다!

문제 링크

https://leetcode.com/problems/merge-intervals/

LeetCode GitHub

https://github.com/tTab1204/LeetCode