【leetcode】57. 插入区间（insert-interval）（模拟）[困难]

链接

https://leetcode-cn.com/problems/insert-interval/

耗时

解题：2 h 17 min
题解：8 min

题意

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

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

思路

分为四种情况：

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

解决：

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

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

AC代码

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>> 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<int> 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;
    }
};