LeetCode 57. Insert Interval

题意

给一个已经分好块的序列，现在要向其中添加一个块，求添加后的块序列

思路

解法一： 直接将新添加的块添加到序列中，然后重新排序进行组合

解法二： 遍历序列，寻找添加块应该处的位置，期间对可以连接的块进行连接.

代码

/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ class Solution { public: vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) { size_t len = intervals.size(); vector<Interval>ans; int i; for(i = 0; i < len; i++){ if(intervals[i].start > newInterval.end){ break; } else if(intervals[i].end >= newInterval.start || (intervals[i].start <= newInterval.end && intervals[i].start >= newInterval.start)){ newInterval.start = min(newInterval.start, intervals[i].start); newInterval.end = max(newInterval.end, intervals[i].end); } else { ans.push_back(intervals[i]); } } ans.push_back(newInterval); for(;i < len;i++) ans.push_back(intervals[i]); return ans; } };