python區間計數，LeetCode 57. 插入區間（python、c++）

題目描述

給出一個無重疊的 ，按照區間起始端點排序的區間列表。

在列表中插入一個新的區間，你需要確保列表中的區間仍然有序且不重疊（如果有必要的話，可以合并區間）。

示例 1：

輸入：intervals = [[1,3],[6,9]], newInterval = [2,5]
輸出：[[1,5],[6,9]]

示例 2：

輸入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
輸出：[[1,2],[3,10],[12,16]]
解釋：這是因為新的區間 [4,8] 與 [3,5],[6,7],[8,10] 重疊。

題解

將該點加入到原來的數組中
1.首先將所有區間按照 start 排序，start 相同的按照 end 排序。
2.從頭開始遍歷所有區間，并求他們的并集。定義 cur 表示當前一些區間的并集。
3.若發現當前遍歷到的區間 start 嚴格大于 cur 的 end，則當前并集需要加入到答案數組中，且更新區間并集 cur 為當前區間。
4.若發現當前遍歷到的區間 end 嚴格大于 cur 的 end，則更新 cur 的 end 為當前區間的 end。
時間復雜度
排序的時間復雜度為 O(nlogn)，排序后只需要線性掃描，故總時間復雜度為 O(nlogn)。

c++代碼：

class Solution {
public:vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {intervals.push_back(newInterval);sort(intervals.begin(), intervals.end());int n = intervals.size();vector<vector<int>> ans;for(int i = 0; i < n; i++){int l = intervals[i][0], r = intervals[i][1];if(!ans.size() || ans.back()[1] < l)ans.push_back({l, r});elseans.back()[1] = max(ans.back()[1], r);}return ans;}
};

python代碼：

class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:intervals.append(newInterval)intervals.sort(key = lambda x: x[0])ans = []for i in intervals:if not ans or ans[-1][1] < i[0]:ans.append(i)else:ans[-1][1] = max(ans[-1][1], i[1])return ans