題目

給你一個 無重疊的 ，按照區間起始端點排序的區間列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 個區間的開始和結束，并且 intervals 按照 starti 升序排列。同樣給定一個區間 newInterval = [start, end] 表示另一個區間的開始和結束。

在 intervals 中插入區間 newInterval，使得 intervals 依然按照 starti 升序排列，且區間之間不重疊（如果有必要的話，可以合并區間）。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以創建一個新數組然后返回它。

思路

這道題和56題合并區間是相同的思路，只不過一個是合并一個是插入。我們還是先思考兩個區間之間存在著什么樣的關系，兩個區間其實只有重疊和不重疊兩種關系，或者是重疊就是一個區間的左邊界大于另外一個區間的左邊界但是小于它的右邊界，而不重疊就是一個區間的左邊界大于另外一個區間的右邊界或者一個區間的右邊界小于另外一個區間的左邊界。理清了這些關系后這道題就好做了。
那么這道題和56題不同的地方在什么呢？在于我們需要插入一個新區間所以我們必須判斷什么時候插入這個新區間，其實就兩種情況一是有比我們還大的區間也就是左邊界都已經大于我們的右邊界了或者是我們直到最后發現新區間還沒有插入也就是說新區間是最后的區間的情況下。所以我們需要定義一個bool類型來判斷新區間是否插入了如果在最后發現它沒插入我們就需要將其插入

代碼

class Solution {
public:vector<vector<int>> insert(vector<vector<int>>& intervals,vector<int>& newInterval) {int L = newInterval[0];int R = newInterval[1];vector<vector<int>> res;bool isInsert = false;for (int i = 0; i < intervals.size(); i++) {// 其實一共就三種情況// 右邊界小于L，直接插入if (intervals[i][1] < L) {res.push_back(intervals[i]);}// 左邊界大于R，先插入[L,R]再插入當前區間else if (intervals[i][0] > R) {if (isInsert == false) {res.push_back({L, R});isInsert = true;}res.push_back(intervals[i]);}// 右邊界大于L，但是小于R或者左邊界小于R但是右邊界大于R，直接更新else {L = min(L, intervals[i][0]);R = max(R, intervals[i][1]);}}// 如果插入區間還沒插入就說明它就是最后一個區間if (isInsert == false) {res.push_back({L, R});}return res;}
};