[LeetCode] 56 Merge Intervals JavaScript

문제 링크

Merge Intervals - LeetCode

 

문제 유형

배열, 정렬

 

문제 풀이

이 문제는 어떤 숫자 배열의 간격들이 요소인 배열이 주어진다. 간격이 겹치는 배열을 합쳐서 최종적으로 겹치지 않는 배열들을 출력한다.

이 문제는 다음과 같은 방식으로 접근한다.

1. 배열을 정렬한다.
   예제 입력은 요소들이 정렬되어 있어 모든 테스트 케이스들이 정렬된 줄 알았는데 테스트 케이스에는 정렬되지 않은 배열도 포함되어 있었다. 따라서, 왼쪽 간격을 기준으로 정렬하되 왼쪽 간격이 같은 경우에는 오른쪽 간격을 기준으로 정렬한다.
2. 겹치는 간격을 찾아 합친다.
    intervals = [[1, 3], [2, 6], [3, 5], [8, 10], [12, 15]]  와 같은 입력이 있다. 합쳐진 배열과 현재 탐색하는 배열의 간격을 비교하여 간격이 겹치는지를 확인한다.
   배열은 정렬되었으므로 현재 합쳐진 배열의 끝 간격보다 현재 배열의 처음 간격이 크면 간격은 겹치지 않는다.
   i = 1 일 때, 현재 탐색할 배열은 [2, 6]이고 합쳐진 배열은 [1, 3]이다. 현재 배열의 처음 간격이 합쳐진 배열의 끝 간격보다 작거나 같으면 겹치므로 두 배열을 합친다.
   i = 2 일 때, 현재 탐색할 배열은 [3, 5]이고 합쳐진 배열은 [1, 6]이다. 두 배열은 겹치지만 현재 배열의 처음과 끝이 합쳐진 배열 내에 포함되므로 합쳐진 배열은 변하지 않는다.

 

코드

var merge = function(intervals) {
    if (intervals.length === 1) return intervals;
    
    intervals.sort((a, b) => a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]); //정렬
    const arr = [intervals[0]];
    
    for (let i = 1; i < intervals.length; i++) {
        const [prevLeft, prevRight] = arr[arr.length - 1];
        const [nowLeft, nowRight] = intervals[i];
        
        if (nowLeft <= prevRight && nowRight > prevRight) { // 끝 간격이 더 크면서 합쳐진 배열과 겹칠 때
            arr[arr.length - 1][1] = nowRight;
        } else if (nowLeft > prevRight) { // 합쳐진 배열과 겹치지 않을 때
            arr.push(intervals[i]);
        }
    }
    return arr;
};

 

참고

https://www.youtube.com/watch?v=S9eQ6DIBPqg