## Question

>[Leetcode.56 Merge Intervals
](https://leetcode.com/problems/merge-intervals/description/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    if(!intervals.length) return [];

    intervals.sort((a,b) => a[0] - b[0]);
    
    const ans = [];
    let curInterval = intervals[0];
    for(let i = 1; i < intervals.length; i++) {
        const [start, end] = intervals[i];
        const curStart = curInterval[0];
        const curEnd = curInterval[1];
        
        if(curEnd < start){
            ans.push(curInterval);
            curInterval = [start, end];
        } else {
            // overlap
            curInterval[1] = Math.max(end, curEnd);
        }
    }
    ans.push(curInterval);

    return ans;
};

:::

<hr/>

### Sol
:::spoiler Code

:::

<hr/>

### 東

:::spoiler Code

// Time - O(nlogn) | Space - O(n) --- n is the number of intervals
 
var merge = function(intervals) {
    intervals.sort((a,b) => a[0] - b[0]);
    const result = [];

    let [currStart, currEnd] = intervals[0];
    for(let i = 1; i < intervals.length; i++) {
        let [start, end] = intervals[i];
        if(currEnd >= start) {
            currEnd = Math.max(currEnd, end);
        } else {
            result.push([currStart, currEnd]);
            currStart = start;
            currEnd = end;
        }
    }

    result.push([currStart, currEnd]);
    return result;
};

:::

<hr/>

### Jessie

:::spoiler Code

var merge = function (intervals) {
    //  合併區間中的 arr

    //  不先 sort 是亂序會有問題
    intervals.sort((a, b) => a[0] - b[0]);

    const result = [intervals[0]];
    //  暴力解: a[1] >= b[0] 就可以合併
    for (let i = 1; i < intervals.length; i++) {
        const currentArr = intervals[i];
        const lastInterval = result[result.length - 1];

        if (lastInterval[1] >= currentArr[0]) {
            lastInterval[1] = Math.max(lastInterval[1], currentArr[1]);
        } else {
            result.push(currentArr);
        }
    }

    return result;
};

:::

<hr/>

### 皮皮

:::spoiler Code

:::

<hr/>

### Howard

:::spoiler Code

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::