Intervals (6) - HackMD

# Intervals (6) > 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主 > > 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)  ## 1. Insert Interval **Medium** > 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: ```java Input: intervals = [[1,3],[4,6]], newInterval = [2,5] Output: [[1,6]] ``` ### Example 2: ```java 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> ```python= 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 **Medium** > 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: ```java Input: intervals = [[1,3],[1,5],[6,7]] Output: [[1,5],[6,7]] ``` ### Example 2: ```java 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]` ![S__2572304](https://hackmd.io/_uploads/rk8sYCH2Jl.jpg) ```python= 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 **Medium** > 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: ```java 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: ```java 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])` ![image](https://hackmd.io/_uploads/SJfmnAH2ke.png) ```python! 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 **Easy** > 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: ```java 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: ```java 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` 就表示重疊 ```python= """ 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 **Medium** > 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: ```java Input: intervals = [(0,40),(5,10),(15,20)] Output: 2 ``` Explanation: day1: (0,40) day2: (5,10),(15,20) ### Example 2: ```java 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` 走完，回傳過程中使用的最多資源數量 ```python= """ 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 **Hard** > 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: ```java 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` 中 ![S__2572313](https://hackmd.io/_uploads/H1pa0MDnJe.jpg) ```python= 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] > 這題的想法不難，只要以圖實際動手操作過流程就知道，麻煩的是在實作上有很多細節需要注意