题目:
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9]
, insert and merge [2,5]
in as [1,5],[6,9]
.
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16]
, insert and merge [4,9]
in as [1,2],[3,10],[12,16]
.
This is because the new interval [4,9]
overlaps with [3,5],[6,7],[8,10]
.
思路: 对于intervals从头到尾遍历,用new interval与相应的interval[i]对比,如果整个new interval都在interval[i]的左边,就把new interval存到result里,然后把剩下的所有interval都存起来即可,如果new interval在interval[i]的右边,则存起来interval[i],然后继续遍历; 如果new interval 和 interval[i]有overlap, 则将两者进行合并,然后继续遍历。
代码:
1 class Solution {
2 public:
3 vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
4 // Start typing your C/C++ solution below
5 // DO NOT write int main() function
6 vector<Interval> result;
7
8 for (int i = 0; i<intervals.size(); i++){
9
10 if (intervals[i].end < newInterval.start)
11 result.push_back(intervals[i]);
12 else if (intervals[i].start>newInterval.end){
13
14 result.push_back(newInterval);
15 while (i<intervals.size()){
16
17 result.push_back(intervals[i]);
18 i++;
19 }
20 }
21
22 else{
23
24 newInterval.start = min(intervals[i].start, newInterval.start);
25 newInterval.end = max(intervals[i].end, newInterval.end);
26
27 }
28 }
29
30 if(0 == result.size() || result.back().end < newInterval.start)
31 result.push_back(newInterval);
32
33 return result;
34 }
35 };
原文链接: https://www.cnblogs.com/tanghulu321/archive/2013/05/11/3072348.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/88097
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!