[LeetCode] 56. Merge Intervals

https://leetcode.com/

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

 

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

 

Constraints:

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

 

Code :

var merge = function(intervals) {
    // 만약 intervals가 비어있다면 빈 배열을 반환합니다.
    if (intervals.length === 0) return [];
    // 배열을 시작값을 기준으로 정렬합니다.
    intervals.sort((a, b) => a[0] - b[0]); 
    // 결과 배열을 생성하고 첫 번째 간격을 추가합니다.
    const result = [intervals[0]];
    // 각 간격을 순회하며 겹치는 부분을 병합합니다.
    for (let i = 1; i < intervals.length; i++) {
        // 현재 간격과 이전 간격을 비교하여 겹치는 부분이 있다면 병합합니다.
        if (intervals[i][0] <= result[result.length - 1][1]) {
            result[result.length - 1][1] = Math.max(result[result.length - 1][1], intervals[i][1]);
        } else {
            // 겹치지 않는다면 새로운 간격으로 추가합니다.
            result.push(intervals[i]);
        }
    }
    // 최종 결과 배열을 반환합니다.
    return result;
};

 

Solutions Code :

var merge = function(intervals) {
    // 결과를 저장할 배열
    let ans = [];
    // 구간을 시작 시점 기준으로 정렬
    intervals.sort((a, b) => a[0] - b[0]);
    // 입력된 구간이 없으면 빈 배열 반환
    if (intervals.length === 0) {
        return ans;
    }
    // 현재 구간을 저장하는 변수
    let temp = intervals[0];
    // 구간을 순회하면서 겹치는 구간을 병합
    for (let i = 0; i < intervals.length; i++) {
        // 현재 구간의 시작점이 temp 구간의 끝점보다 작거나 같으면 겹침
        if (intervals[i][0] <= temp[1]) {
            // temp 구간의 끝점을 갱신
            temp[1] = Math.max(temp[1], intervals[i][1]);
        } else {
            // 겹치지 않으면 현재 temp 구간을 결과에 추가하고 temp 갱신
            ans.push(temp);
            temp = intervals[i];
        }
    }
    // 마지막으로 남은 temp 구간을 결과에 추가
    ans.push(temp);
    // 최종 결과 반환
    return ans;
};

 

 

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

Problems - LeetCode