本文共 1355 字，大约阅读时间需要 4 分钟。

链接

耗时

解题：2 h 17 min

题意

给出一个无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

思路

分为四种情况：

1. 在头部插入
2. 在结尾插入
3. 在中间插入
4. 与某些现存区间合并

解决：

1. 判断是否为空，新增区间右端点是否小于列表第一个区间左端点。
2. 不在中间插入或合并，就在结尾插入
3. 在现存区间之间，但不能与现存区间合并
4. 先找到 新增区间左端点 的插入位置，再找到 新增区间右端点 的插入位置，合并这之间的区间

时间复杂度：$O(n)$

AC代码

class Solution {   public:    vector
   
    
     > insert(vector
     
      
       >& intervals, vector
       
        & newInterval) {           int l = newInterval[0];        int r = newInterval[1];        vector
        
         
          > ans; bool flag = true; int n = intervals.size(); // no merge, begin add new interval if(intervals.empty() || r < intervals[0][0]) { ans.push_back(newInterval); flag = false; } for(int i = 0; i < n; ++i) { vector
          
            tmp = { intervals[i][0], intervals[i][1]}; if(flag) { if(l <= intervals[i][0] || l <= intervals[i][1]) { int pos = i; tmp[0] = min(l, intervals[i][0]); while(i < n && (r > intervals[i][0] && r > intervals[i][1])) i++; if(i == n) { tmp[1] = r; } else { if(r < intervals[i][0]) { tmp[1] = r; if(i != pos) i -= 1; } else { tmp[1] = max(r, intervals[i][1]); } } // middle add new interval if(pos == i && (l < intervals[i][0] && r < intervals[i][0])) i -= 1; flag = false; } } ans.push_back(tmp); } // no merge, end add new interval if(flag) { ans.push_back(newInterval); } return ans; }};