（每日一练c++）57. 插入区间

梦里梦外; 2023-10-04 18:19 29阅读 0赞

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

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

示例 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\] 重叠。  
示例 3：

输入：intervals = \[\], newInterval = \[5,7\]  
输出：\[\[5,7\]\]  
示例 4：

输入：intervals = \[\[1,5\]\], newInterval = \[2,3\]  
输出：\[\[1,5\]\]  
示例 5：

输入：intervals = \[\[1,5\]\], newInterval = \[2,7\]  
输出：\[\[1,7\]\]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/insert-interval  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public:
        vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
            int left = newInterval[0];
            int right = newInterval[1];
            bool placed = false;
            vector<vector<int>> ans;
            for (const auto& interval: intervals) {
                if (interval[0] > right) {
                    // 在插入区间的右侧且无交集
                    if (!placed) {
                        ans.push_back({left, right});
                        placed = true;                    
                    }
                    ans.push_back(interval);
                }
                else if (interval[1] < left) {
                    // 在插入区间的左侧且无交集
                    ans.push_back(interval);
                }
                else {
                    // 与插入区间有交集，计算它们的并集
                    left = min(left, interval[0]);
                    right = max(right, interval[1]);
                }
            }
            if (!placed) {
                ans.push_back({left, right});
            }
            return ans;
        }
    };
    
    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/insert-interval/solution/cha-ru-qu-jian-by-leetcode-solution/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。