56. Merge Intervals

Loading...LeetCode

time: O(n)

space: O(1)

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */

/**
case 1
[true, true, true,  true, false, ....] <<

____ (0, 3)
 __ (1, 2)
  _____
        ___
             ____
                _
                ____
                  ____
                       ___

[true, true, true,  false, true, ....] <<

____________ _____________

[[0, 6], [8, 15]]

max(n^2, length(min, max))
length(min, max)

*/

/**
case 2

>>1
_____
 ___

>>2
_____
 _____

>>3
_____
      _____

>>4
_____
     _____

2, 4 통합 가능

with intervals a, b 

merge = interval to check

start with merge = a, [1, 3]

1. check merge[1] < b[0]
2. yes, merge = b; 
    next
3. no
4. check merge[1] < b[1]
5. yes, merge = [merge[0], b[1]]
    next
6. no, merge = merge
    next

 */

var merge = function(intervals) {
    let answer = [];

    intervals.sort((a, b) => a[0] - b[0]);

    let merged = intervals[0];
    for (let i = 0; i < intervals.length; i++) {
        const curr = intervals[i];

        if (merged[1] < curr[0]) {
            answer.push(merged);
            merged = curr;
        } else if (merged[1] >= curr[0]){
            if (merged[1] < curr[1]) {
                merged[1] = curr[1];
            }
            // merged[1] = Math.max(merged[1], curr[1])
        }
    }

    answer.push(merged);

    return answer;
};