(Leet Code JS)Merge Intervals

56. Merge Intervals

 

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] overlaps, 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 <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

주어진 intervals를 오름차순으로 정렬한다.

정렬을 한 후, front와 back을 intervals[0][0], intervals[0][1]로 초기값을 설정한 후 탐색 진행.

 

만약 back이 intervals[i][0]보다 작으면, 지금까지의 오버랩 된 수를 answer에 넣어준다.

그리고 front와 back을 intervals[i]에 있는 수로 저장.

 

그렇지 않고, back이 intervals[i][1]보다 작으면 back만 intervals[i][1]로 바꿔 오버랩을 진행한다.

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    const answer = [];
    let front = 0, back = 0;
    
    intervals.sort((a, b) => {
        if(a[0] === b[0]){
            return a[1] - b[1];
        }
        else{
            return a[0] - b[0];
        }
    });
    
    front = intervals[0][0];
    back = intervals[0][1];
    
    for(let i = 1; i < intervals.length; i++){
        if(back < intervals[i][0]){
            answer.push([front, back]);
            front = intervals[i][0];
            back = intervals[i][1];
        }
        else if(back < intervals[i][1]){
            back = intervals[i][1];
        }
    }
    
    answer.push([front, back]);
    
    return answer;
};