# Intervals (6)

> 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主
>
> 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)

<!-- 常用色碼紀錄
Easy: <font color="#00ad5f">**Easy**</font>
Medium: <font color="#ffbb00">**Medium**</font>
Hard: <font color="#ee2f56">**Hard**</font>
-->

## 1. Insert Interval
<font color="#ffbb00">**Medium**</font>

> You are given an array of non-overlapping intervals `intervals` where `intervals[i] = [start_i, end_i]` represents the start and the end time of the `ith` interval. `intervals` is initially sorted in ascending order by `start_i`.
>
> You are given another interval `newInterval = [start, end]`.
>
> Insert `newInterval` into `intervals` such that `intervals` is still sorted in ascending order by `start_i` and also `intervals` still does not have any overlapping intervals. You may merge the overlapping intervals if needed.
>
> Return `intervals` after adding `newInterval`.
>
> Note: Intervals are *non-overlapping* if they have no common point. For example, [1,2] and [3,4] are non-overlapping, but [1,2] and [2,3] are overlapping.

### Example 1:

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

Output: [[1,6]]

### Example 2:

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

Output: [[1,2],[3,5],[6,7],[9,10]]

### Constraints

* `0 <= intervals.length <= 1000`
* `newInterval.length == intervals[i].length == 2`
* `0 <= start <= end <= 1000`

### Recommended complexity:

* Time complexity: $O(n)$
* Space complexity: $O(1)$ extra space

### Solution

要考慮新區間 `newInterval` 應該插入到剩餘 `intervals` 中的哪個位置

* 放第一個: `newInterval[1] < intervals[0][0]`
* 放最後一個: `newInterval[0] > intervals[-1][0]`
* 放中間: 要考慮需不需要合併
* 不需合併: `newInterval[0] > intervals[i][1]`
* 需合併: 把 `newInterval` 更新為合併後的新範圍(見下圖)

<img src="https://hackmd.io/_uploads/rksiIABnJg.jpg" width=600>

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []

        for i in range(len(intervals)):
            # insert at beginning
            if newInterval[1] < intervals[i][0]:
                res.append(newInterval)
                return res + intervals[i:]
            
            # insert behind intervals[i]
            elif intervals[i][1] < newInterval[0]:
                res.append(intervals[i])
            
            # overlapping: merge
            else:
                newInterval = [min(newInterval[0], intervals[i][0]), 
                               max(newInterval[1], intervals[i][1])]
        
        # insert at the end
        res.append(newInterval)

        return res

## 2. Merge Intervals
<font color="#ffbb00">**Medium**</font>

> Given an array of `intervals` where `intervals[i] = [start_i, end_i]`, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
>
> You may return the answer in **any order**.
>
> Note: Intervals are non-overlapping if they have no common point. For example, `[1, 2]` and `[3, 4]` are non-overlapping, but `[1, 2]` and `[2, 3]` are overlapping.

### Example 1:

Input: intervals = [[1,3],[1,5],[6,7]]

Output: [[1,5],[6,7]]

### Example 2:

Input: intervals = [[1,2],[2,3]]

Output: [[1,3]]

### Constraints

* `1 <= intervals.length <= 1000`
* `intervals[i].length == 2`
* `0 <= start <= end <= 1000`

### Recommended complexity

* Time complexity: as good or better than $O(n \cdot \log n)$
* Space complexity: $O(n)$

### Solution

(1) 先對 `intervals` 依照 start time 排序
(2) 排序後從 start time 最小的開始做迭代，檢查哪些 `interval` 需要做合併(下圖)

* merged: 之前已經合併後的 interval
* 若 `interval[i][0] <= merge[1]` 表示需要合併
* 與 merged 相比選擇較小的 start time 與較大的 finish time 作為合併後的結果
* 否則不需要合併
* 之前的 merged 加到結果中
* 更新 merge 為下一個範圍 `interval[i]`


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda pair: pair[0])

        res = []
        merge = [intervals[0][0], intervals[0][1]]

        for i in range(len(intervals)):
            if intervals[i][0] <= merge[1]:
                merge = [min(merge[0], intervals[i][0]),
                         max(merge[1], intervals[i][1])]
            else:
                res.append(merge)
                merge = [intervals[i][0], intervals[i][1]]
        
        res.append(merge)
        return res

## 3. Non-overlapping Intervals
<font color="#ffbb00">**Medium**</font>

> Given an array of intervals `intervals` where `intervals[i] = [start_i, end_i]`, return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note: Intervals are non-overlapping even if they have a common point. For example, `[1, 3]` and `[2, 4]` are overlapping, but `[1, 2]` and `[2, 3]` are non-overlapping.

### Example 1:

Input: intervals = [[1,2],[2,4],[1,4]]

Output: 1

Explanation: After [1,4] is removed, the rest of the intervals are non-overlapping.

### Example 2:

Input: intervals = [[1,2],[2,4]]

Output: 0

### Constraint

* `1 <= intervals.length <= 1000`
* `intervals[i].length == 2`
* `-50000 <= starti < endi <= 50000`

### Recommended complexity

* Time complexity: $O(n \cdot \log n)$
* Space complexity: $O(n)$

### Solution

(1) 先對 start time 做排序
(2) 以 `prevEnd` 紀錄目前最後結束的時間點，檢查每個 `interval` 有沒有重疊

* 不重疊時
* `intervals[i][0] >= prevEnd`
* 更新 `prevEnd` 為下一個 `interval` 的 finish time
* 重疊時
* `intervals[i][0] < prevEnd`
* 應該刪除結束時間比較大的 `interval`，因為 finish time 越大，後面能塞的 interval 越少，表示要刪除的會越多
* 更新 `prevEnd = min(prevEnd, intervals[i][1])`


class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda pair: pair[0])

        prevEnd = intervals[0][1]
        res = 0

        for i in range(1, len(intervals)):
            # not overlapping
            if intervals[i][0] >= prevEnd:
                prevEnd = intervals[i][1]
            
            # overlapping
            else:
                prevEnd = min(prevEnd, intervals[i][1])
                res += 1
            
        return res

## 4. Meeting Rooms
<font color="#00ad5f">**Easy**</font>

> Given an array of meeting time interval objects consisting of start and end times `[[start_1,end_1],[start_2,end_2],...] (start_i < end_i)`, determine if a person could add all meetings to their schedule without any conflicts.

### Example 1:

Input: intervals = [(0,30),(5,10),(15,20)]

Output: false

Explanation:

* `(0,30)` and `(5,10)` will conflict
* `(0,30)` and `(15,20)` will conflict

### Example 2:

Input: intervals = [(5,8),(9,15)]

Output: true

Note:

* (0,8),(8,10) is not considered a conflict at 8

### Constraints

* `0 <= intervals.length <= 500`
* `0 <= intervals[i].start < intervals[i].end <= 1,000,000`

### Recommended complexity

* Time complexity: $O(n \cdot \log n)$
* Space complexity: $O(n)$

### Solution

不能安排計劃表示形成間有重疊的時間點:

* 先對每個物件的 start 屬性排序
* 只要某物件的 `start` <= 前一個物件的 `end` 就表示重疊

"""
Definition of Interval:
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""

class Solution:
    def canAttendMeetings(self, intervals: List[Interval]) -> bool:
        if not intervals:
            return True
            
        intervals.sort(key = lambda obj: obj.start)
        
        st = intervals[0].start
        ed = intervals[0].end
        for i in range(1, len(intervals)):
            if intervals[i].start < ed:
                return False
            else:
                st = intervals[i].start
                ed = intervals[i].end
        
        return True

## 5. Meeting Rooms II
<font color="#ffbb00">**Medium**</font>

> Given an array of meeting time interval objects consisting of start and end times `[[start_1,end_1],[start_2,end_2],...] (start_i < end_i)`, find the minimum number of days required to schedule all meetings without any conflicts.

### Example 1:

Input: intervals = [(0,40),(5,10),(15,20)]

Output: 2

Explanation:
day1: (0,40)
day2: (5,10),(15,20)

### Example 2:

Input: intervals = [(4,9)]

Output: 1

Note:

* (0,8),(8,10) is not considered a conflict at 8

### Constraints

* `0 <= intervals.length <= 500`
* `0 <= intervals[i].start < intervals[i].end <= 1,000,000`

### Recommended complexity

* Time complexity: $O(n \cdot \log n)$
* Space complexity: $O(n)$

### Solution

這題跟 [Lecture 04: Greedy algorithm](/afku67hVTjuDmknsaezhYQ) 中的 intervals partition 一樣，需要使用最少的資源來完成所有的 interval，畫出時間軸可知破題重點。

<img src="https://hackmd.io/_uploads/Bkxs0GDnJe.jpg" width=500>

如上圖，同一時間佔用的最多資源數 = 完成所有工作所需最少資源數。因為資源的使用跟 start time 與 end time 有關，所以對所有 interval 的 start/end time 做排序

* 以 start/end time 各自組成一個 sorted array: `startTime` 與 `endTime`
* 以兩個指標各自指向 `startTime` 與 `endTime`
* 當 `startTime[i] < endTime[j]` 表示使用一個資源
* `count++`
* `i++`
* 當 `startTime[i] < endTime[j]` 表示釋放一個資源
* `count--`
* `j++`
* 當 `startTime[i] = endTime[j]` 表示先使用資源再釋放資源
* `i++`
* `j++`
* 直到 `startTime` 走完，回傳過程中使用的最多資源數量

"""
Definition of Interval:
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""

class Solution:
    def minMeetingRooms(self, intervals: List[Interval]) -> int:
        startTime = []
        endTime = []
        for I in intervals:
            startTime.append(I.start)
            endTime.append(I.end)
        
        startTime.sort()
        endTime.sort()

        ptrSt, ptrEd = 0, 0
        cnt, res = 0, 0
        while ptrSt < len(startTime):
            # add resource
            if startTime[ptrSt] < endTime[ptrEd]:
                cnt += 1
                ptrSt += 1
            # release resource
            elif startTime[ptrSt] > endTime[ptrEd]:
                cnt -= 1
                ptrEd += 1
            # add then release
            else:
                ptrSt += 1
                ptrEd += 1
            
            res = max(cnt, res)
        return res

## 6. Minimum Interval to Include Each Query
<font color="#ee2f56">**Hard**</font>

> You are given a 2D integer array `intervals`, where `intervals[i] = [left_i, right_i]` represents the `ith` interval starting at `left_i` and ending at `right_i` **(inclusive)**.
>
> You are also given an integer array of query points `queries`. The result of `query[j]` is the **length of the shortest interval** `i` such that `left_i <= queries[j] <= right_i`. If no such interval exists, the result of this query is `-1`.
>
> Return an array `output` where `output[j]` is the result of `query[j]`.
>
> Note: The length of an interval is calculated as `right_i - left_i + 1`.

### Example 1:

Input: intervals = [[1,3],[2,3],[3,7],[6,6]], queries = [2,3,1,7,6,8]

Output: [2,2,3,5,1,-1]

Explanation:

* Query = 2: The interval `[2,3]` is the smallest one containing 2, it's length is 2.
* Query = 3: The interval `[2,3]` is the smallest one containing 3, it's length is 2.
* Query = 1: The interval `[1,3]` is the smallest one containing 1, it's length is 3.
* Query = 7: The interval `[3,7]` is the smallest one containing 7, it's length is 5.
* Query = 6: The interval `[6,6]` is the smallest one containing 6, it's length is 1.
* Query = 8: There is no interval containing 8.

### Constraints

* `1 <= intervals.length <= 1000`
* `1 <= queries.length <= 1000`
* `1 <= left_i <= right_i <= 10000`
* `1 <= queries[j] <= 10000`

### Recommended complexity

* Time complexity: as good or better than $O(n \cdot \log n + m \cdot \log m)$
* n is the size of the array `intervals`
* m is the size of the array `queries`
* Space complexity: as good or better than $O(n + m)$

### Solution

(1) 對每一個 `queries[i]` 檢查哪些 inteval 是可能的區間:

* 符合 `left_i <= queries[i]` 才有可能
* 紀錄可能的 interval 的 length 和 `right_i`

因為要找最小的 length，所以可用 minHeap 加速尋找過程。將上述可能的 interval 以 `(len, right_i)` 的形式推(push)到 minHeap 中

(2) 同樣再對 `queries[i]` 找正確且最小 length 的區間。

從 minHeap 找最小的 length，但找出來的區間可能不包含 `queries[i]` (因為 `right_i` 太小)。所以必須刪除不合格的 interval

* 從 minHeap 找到最小 length 後檢查不合格: `right_i < queries[j]`
* 如果是合理的，則它的 length 即為所求: 加到 `res` 中


class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals.sort()
        minHeap = []
        res = {}
        i = 0 # pointer

        for q in sorted(queries):
            while i < len(intervals) and intervals[i][0] <= q:
                left, right = intervals[i][0], intervals[i][1]
                size = right - left + 1
                heapq.heappush(minHeap, (size, right))
                i += 1
                
            while minHeap and minHeap[0][1] < q: # invalid pair
                heapq.heappop(minHeap)

            if minHeap:
                res[q] = minHeap[0][0] # size
            else: # minHeap is empty
                res[q] = -1
            
        return [res[q] for q in queries]

> [!Caution]
> 這題的想法不難，只要以圖實際動手操作過流程就知道，麻煩的是在實作上有很多細節需要注意