## Question

>[Leetcode.57 Insert Interval
](https://leetcode.com/problems/insert-interval/description/)

<br>

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

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

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function(intervals, newInterval) {
    if (!intervals.length) return [newInterval];
    
    const ans = [];
    for (const interval of intervals){
        if (interval[1] < newInterval[0]) {
            // interval < newInterval 
            ans.push(interval);
        }
        else if (newInterval[1] < interval[0]) {
            // newInterval < interval
            ans.push(newInterval);
            newInterval = interval;
        }
        else {
            // overlap
            const min = Math.min(interval[0], newInterval[0]);
            const max = Math.max(interval[1], newInterval[1]);
            newInterval = [min, max]
        }
    }
    ans.push(newInterval);
    return ans;
};

:::

<hr/>

### Sol
:::spoiler Code

:::

<hr/>

### 東

:::spoiler Code

// Time O(n) | Space O(n) - n is the length of input intervals
var insert = function(intervals, newInterval) {
    let i = 0;
    const result = [];

    while(i < intervals.length && intervals[i][1] < newInterval[0]) {
        result.push(intervals[i]);
        i++;
    }

    let insertInterval = [...newInterval];
    while(i < intervals.length && intervals[i][0] <= newInterval[1]) {
        insertInterval[0] = Math.min(insertInterval[0], intervals[i][0]);
        insertInterval[1] = Math.max(insertInterval[1], intervals[i][1]);
        i++;
    }
    result.push(insertInterval);

    while(i < intervals.length) {
        result.push(intervals[i]);
        i++;
    }

    return result;
}

:::

<hr/>

### Jessie

:::spoiler Code

  // * Case 1: 當 current[1] < new[0], current 不用動
  // arr = [[1,3],[6,9]]   new = [4,5]
  // Result = [[1,5],[4,5],[6,9]]

  // * Case 2:當 current[0] > new[1], current[0] = Min(new[0], current[0])
  // arr = [[1,3],[6,9]]   new = [4,6]
  // Result = [[1,3],[4,9]]

  // * Case 3: 當 current[1] >= newInterval[0] && current[0] <= newInterval[1], current[1] = Max(new[1], current[1])
  // arr = [[1,3],[6,9]]   new = [2,5]
  // Result = [[1,5],[6,9]]

:::

<hr/>

### 皮皮

:::spoiler Code

:::

<hr/>

### Howard

:::spoiler Code

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::