57.Insert Interval
===

###### tags: `Medium`,`Array`

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

### 題目描述
You are given an array of non-overlapping intervals `intervals` where `intervals[i]` = [$start_i$, $end_i$] represent the start and the end of the i^th^ interval and `intervals` is sorted in ascending order by $start_i$. You are also given an interval `newInterval` = `[start, end]` that represents the start and end of another interval.

Insert `newInterval` into `intervals` such that intervals is still sorted in ascending order by $start_i$ and `intervals` still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return `intervals` *after the insertion.*

### 範例

**Example 1:**

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

**Example 2:**

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

**Constraints**:

* 0 <= intervals.length <= 10^4^
* `intervals[i].length` == 2
* 0 <= $start_i$ <= $end_i$ <= 10^5^
* `intervals` is sorted by $start_i$ in **ascending** order.
* `newInterval.length` == 2
* 0 <= `start` <= `end` <= 10^5^

### 解答

#### Javascript

function insert(intervals, newInterval) {
  const newIntervals = [];
  for (const interval of intervals) {
    if (interval[1] < newInterval[0]) {
      newIntervals.push(interval);
    } else if (interval[0] > newInterval[1]) {
      newIntervals.push(newInterval);
      newInterval = interval;
    } else {
      newInterval[0] = Math.min(interval[0], newInterval[0]);
      newInterval[1] = Math.max(interval[1], newInterval[1]);
    }
  }

  newIntervals.push(newInterval);

  return newIntervals;
}

> [name=Marsgoat] [time= Jan 16, 2023]

function insert2(intervals, newInterval) {
  const newIntervals = [];
  for (const [start, end] of intervals) {
    const [newStart, newEnd] = newInterval;
    if (end < newStart) {
      newIntervals.push([start, end]);
    } else if (start > newEnd) {
      newIntervals.push(newInterval);
      newInterval = [start, end];
    } else {
      newInterval = [Math.min(start, newStart), Math.max(end, newEnd)];
    }
  }

  newIntervals.push(newInterval);

  return newIntervals;
}

function insert3(intervals, newInterval) {
  const newIntervals = [];
  const start = 0;
  const end = 1;
  for (const interval of intervals) {
    if (interval[end] < newInterval[start]) {
      newIntervals.push(interval);
    } else if (interval[start] > newInterval[end]) {
      newIntervals.push(newInterval);
      newInterval = interval;
    } else {
      newInterval[start] = Math.min(interval[start], newInterval[start]);
      newInterval[end] = Math.max(interval[end], newInterval[end]);
    }
  }

  newIntervals.push(newInterval);

  return newIntervals;
}

> 看到有人會把數字換成文字，不知道大家覺得2跟3哪個好，這樣可讀性真的有比較高嗎？
> [name=Marsgoat] [time= Jan 17, 2023]

#### C++
##### 思路:
1. 找到插入位置, 合併時, 區間起始取最小, 結束取最大

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int insert_start = newInterval[0], insert_end = newInterval[1];
        for(int i = 0; i < intervals.size(); i++)
        {
            auto& v = intervals[i];
            int cur_start = v[0], cur_end = v[1];
            if(insert_start > cur_end)
                res.push_back(v);
            else if(cur_start > insert_end)
            {
                res.push_back({insert_start, insert_end});
                while(i < intervals.size())
                {
                    res.push_back(intervals[i]);
                    i++;
                }
                return res;
            }
            else
            {
                insert_start = min(insert_start, cur_start);
                insert_end = max(insert_end, cur_end);
            }
        }
        res.push_back({insert_start, insert_end});
        return res;
    }
};

> [name=XD] [time= Jan 16, 2023]

Time: $O(n)$
Extra Space: $O(n)$

#### Python

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        def does_intervals_overlap(a, b):
            return min(a[1], b[1]) - max(a[0], b[0]) >= 0

        def merge_intervals(a, b):
            return min(a[0], b[0]), max(a[1], b[1])

        isIntervalInserted = False
        for i, interval in enumerate(intervals):
            if newInterval[0] < interval[0]:
                index = i
                isIntervalInserted = True
                break

        if isIntervalInserted:
            intervals.insert(index, newInterval)
        else:
            intervals.append(newInterval)

        ans, i = [], 0
        while i < len(intervals):
            curr_interval = intervals[i]

            while i < len(intervals) and does_intervals_overlap(curr_interval, intervals[i]):
                curr_interval = merge_intervals(curr_interval, intervals[i])
                i += 1

            ans.append(curr_interval)

        return ans

> [name=Ron Chen] [time= Jan 17, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)