57. 插入区间（区间问题）

链接57. 插入区间题解1.找到newInterval的在新集合result的插入位置找到interval中的起点比newInterval的起点要大就停止2.单独判断newInterval和result.back().end的大小情况将newInterval放入的result3.对后面的intervals判断集合区间放入result中class Solution { public: vectorvectorint insert(vectorvectorint intervals, vectorint newInterval) { // 1.区间无重合 vectorvectorint result; if (intervals.size() 0) { result.push_back(newInterval); return result; } int start 0; for (start 0; start intervals.size(); start) { if (intervals[start][0] newInterval[0]) { result.push_back(intervals[start]); } else { break; } } // 将newInterval插入 if (!result.empty() result.back()[1] newInterval[0]) { result.back()[1] max(result.back()[1], newInterval[1]); } else { result.push_back(newInterval); } for (int i start; i intervals.size(); i) { if (result.back()[1] intervals[i][0]) { // 更新end末尾 result.back()[1] max(result.back()[1], intervals[i][1]); } else { result.push_back(intervals[i]); } } // RVO return result; } };class Solution { public: vectorvectorint insert(vectorvectorint intervals, vectorint newInterval) { int left newInterval[0]; int right newInterval[1]; bool placed false; vectorvectorint 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; } };/** * Definition of Interval: * class Interval { * public: * int start, end; * Interval(int start, int end) { * this-start start; * this-end end; * } * } */ class Solution { public: /** * param intervals: Sorted interval list. * param newInterval: new interval. * return: A new interval list. */ vectorInterval insert(vectorInterval intervals, Interval newInterval) { // write your code here if (intervals.size() 0) { return intervals; } intervals.push_back(newInterval); sort(intervals.begin(), intervals.end(), [](const Interval a, const Interval b) { return a.start b.start ? true : false; }); vectorInterval result; result.push_back(intervals[0]); for (int i 1; i intervals.size(); i) { if (result.back().end intervals[i].start) { result.back().end max(result.back().end, intervals[i].end); } else { result.push_back(intervals[i]); } } return result; } };