56. Merge Intervals

난이도: 중간 (Medium)

링크: LeetCode 56

풀이 날짜: 2025/10/21

 

1. 문제 이해

여러 구간(interval)이 주어졌을 때, 겹치는 구간을 병합하고, 겹치지 않는 구간은 그대로 유지한다.

 

2. 접근 방식 — 정렬 + 병합

핵심 아이디어: 시작값 기준으로 정렬 후, 연속되는 구간을 병합한다.

1. intervals를 시작값 기준으로 오름차순 정렬
2. current 변수에 현재 병합 중인 구간 저장
3. 반복문으로 각 구간과 current 비교:
   • 겹치는 경우(current[1] >= intervals[i][0]): current[1] = max(current[1], end) → 끝값 갱신
   • 겹치지 않는 경우(current[1] < intervals[i][0]): current를 결과 배열에 push, current 갱신

 

3. 풀이 코드

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

  const result = [];
  let current = intervals[0];

  for(let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];

    if(start <= current[1]) {
      // 겹치면 끝값 갱신
      current[1] = Math.max(current[1], end);
    } else {
      // 겹치지 않으면 결과에 push
      result.push(current);
      current = [start, end];
    }
  }

  result.push(current); // 마지막 구간 추가

  return result;
};

• 정렬 후 연속 구간을 비교 → O(n log n + n)
• 정렬을 먼저 하지 않으면 겹치는 구간이 뒤쪽에 나타나 병합이 어려움
• 병합 시에는 단순히 끝값(max) 갱신 → 불필요한 반복 제거

예시 시나리오

입력: [[1,3],[2,6],[8,10],[15,18]]

current	비교 구간	병합 여부	결과
[1,3]	[2,6]	O	current = [1,6]
[1,6]	[8,10]	X	result.push([1,6]), current=[8,10]
[8,10]	[15,18]	X	result.push([8,10]), current=[15,18]
마지막	-	-	result.push([15,18])

최종 결과 → [[1,6],[8,10],[15,18]]

시간 및 공간 복잡도

항목	복잡도	설명
시간 복잡도	O(n log n)	정렬: O(n log n), 순회: O(n)
공간 복잡도	O(n)	결과 배열 저장

 

4. 핵심 정리

개념	설명
문제 유형	Array, Sorting, Interval
핵심 아이디어	시작값 기준 정렬 후, 연속 구간은 끝값 갱신, 겹치지 않으면 결과에 push
핵심 변수	current, result, [start,end]
시간 복잡도	O(n log n)
공간 복잡도	O(n)
포인트	정렬 후 단일 순회 → 효율적 병합, 끝값 갱신으로 중복 계산 제거