# 資訊

:::info
- Question: 57. Insert Interval
- From: Leetcode Daily Challenge 2024.03.17
- Difficulty: Medium
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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.

Note that you don't need to modify intervals in-place. You can make a new array and return it.

> Example 1:
:::success
- Input: `intervals = [[1,3],[6,9]]`, `newInterval = [2,5]`
- Output: `[[1,5],[6,9]]`
:::

> Example 2:
:::success
- 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:
:::success
- 0 <= `intervals.length` <= $10^4$
- `intervals[i].length` == 2
- 0 <= `starti` <= `endi` <= $10^5$
- `intervals` is sorted by `starti` in ascending order
- `newInterval.length` == 2
- 0 <= start <= end <= $10^5$
:::

---

# 解法

## 概念

簡單的 array 題，感覺就是有沒有想好所有情況而已

我的方法核心觀念是：把所有跟 `newInterval` 有 overlapping 的 interval 都 merge 到 `newInterval` 裡面，最後在適當的時機 append 到 `ans` 裡面

至於什麼是有 overlapping 到，這會分成幾種情況
1. overlapping 到前面而已（這會連帶考慮到 `newInterval` $\in$ `interval`）
2. overlapping 到後面而已（這會連帶考慮到 `interval` $\in$ `newInterval`）
而這兩種情況其實也就夠了！可以看程式碼第 16 - 19 行的實作

最後小細節就是要注意 `newInterval` 有沒有確實且適切的 append 上 `ans`，這就分成第 12 - 14 行 merge 完後的 append 和 `newInterval` 本來就比 `intervals` 裡面任何一個 interval 還小時，進 for loop 就應該先 append 的第 8 - 10 行，當然還有最後 for loop 都沒有 append 上去的第 21 - 22 行處理，最後的部分是應付 merge 有做到 `intervals[-1]` 這種情況

## 程式碼

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        ans = []
        appendFlag = 0
        modFlag = 0

        for e in intervals:
            if appendFlag == 0 and e[0] > newInterval[1]:
                ans.append( newInterval )
                appendFlag = 1
            if e[1] < newInterval[0] or e[0] > newInterval[1]:
                if appendFlag == 0 and modFlag == 1:
                    ans.append( newInterval )
                    appendFlag = 1
                ans.append( e )
            elif ( e[0] <= newInterval[0] and e[1] >= newInterval[0] ) or ( e[0] <= newInterval[1] and e[1] >= newInterval[1] ):
                newInterval[0] = min( e[0], newInterval[0] )
                newInterval[1] = max( e[1], newInterval[1] )
                modFlag = 1
        
        if appendFlag == 0:
            ans.append( newInterval )

        return ans

---

# 複雜度

## 時間複雜度

會跑過每一個元素，看要 merge 還是 append，所以會是 $O(n)$


## 空間複雜度

創了一個回傳陣列，是 $O(n)$