插入某个区间,然后输出合并后的结果。
偷了个懒,此题直接借用上题的合并即可。
但是实际上,题中说已经排好序了。
所以时间复杂度可以降到o(n)
int cmp(Interval a,Interval b) { if(a.start == b.start) return a.end < b.end; return a.start < b.start; } class Solution { public: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { intervals.push_back(newInterval); return merge(intervals); } private: vector<Interval> merge(vector<Interval> &intervals) { sort(intervals.begin(),intervals.end(),cmp); vector<Interval> ans; ans.clear(); if(intervals.size() <= 0)return ans; Interval item = intervals[0]; for(int i = 1;i < intervals.size();i++) { if(item.end < intervals[i].start) { ans.push_back(item); item = intervals[i]; } else { if(item.end < intervals[i].end) item.end = intervals[i].end; } } ans.push_back(item); return ans; } };