Leetcode 56. Merge Intervals - 자바스크립트

56. Merge Intervals - https://leetcode.com/problems/merge-intervals/

1. 문제 설명

2차원 배열로 구성된 intervals 에서 오버래핑되는 구간을 병합하여 합친후 return하는 문제.

2. 풀이

구간을 먼저 정렬한다. 정렬의 기준은 start 즉, 각 원소의 0번 인덱스를 기준으로 정렬. 자바스크립트에서 제공하는 sort 메서드는 ASCII 문자열을 기준으로 정렬하므로 숫자정렬을 위해선 compare option을 넣어 숫자를 정렬해야한다.

이후, 가장 초기값(첫번째 구간)을 넣고 다음 시작점이 자신보다 작을 경우 한번 더 끝점을 비교해 후보에 올라있는 구간을 병합한다. 만약 다음 시작점이 후보배열 종료점보다 클 경우는 새로운 구간으로 push하여 저장한다.

3. 정답 코드

const merge = (intervals) => {
    intervals.sort((a, b) => {
        return a[0] - b[0]
    })

    const answer = [[...intervals[0]]];
    for (let i=1; i < intervals.length; i++) {
        const lastIdx = answer.length-1;
        
        if (answer[lastIdx][1] >= intervals[i][0]) {
            if (answer[lastIdx][1] < intervals[i][1]) {
                answer[lastIdx][1] = intervals[i][1]
            }
        } else {
            answer.push([...intervals[i]])
        }
    }
    return answer;
};