循环遍历原有区间,将待插入区间的右端点、左端点分别与当前区间比较,并更新待插入区间的左右端点,代码如下:
// // Created by jt on 2020/9/29. // #include <vector> using namespace std; class Solution { public: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { vector<Interval> res; int i = 0; for (; i < intervals.size(); ++i) { // 如果新区间的右边界小于当前区间的左边界,终止循环 // 如果新区间和当前区间有重叠,更新新区间的左右边界 // 如果新区间的左边界大于当前区间的右边界,将当前区间放入结果 if (newInterval.end < intervals[i].start) break; else if (newInterval.start <= intervals[i].end) { newInterval.start = min(newInterval.start, intervals[i].start); newInterval.end = max(newInterval.end, intervals[i].end); } else res.push_back(intervals[i]); } // 将更新后的新区间放入结果 res.push_back(newInterval); // 将剩余的区间放入结果 while(i < intervals.size()) { res.push_back(intervals[i]); ++i; } return res; } };