【leetcode】Insert Interval

地址

https://leetcode.com/problems/insert-interval/description/

题目

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: Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]

Example 2: Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

思路

模拟下就好了,没什么好说的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
* 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>& va, Interval vb) {
vector<Interval> ans;
Interval tmp;
int n=va.size();
if(n==0)
{
ans.push_back(vb);
return ans;
}
if(vb.start > va[n-1].end)
{
for(int i=0; i<n; i++) ans.push_back(va[i]);
ans.push_back(vb);
return ans;
}
if(vb.end < va[0].start)
{
ans.push_back(vb);
for(int i=0; i<n; i++) ans.push_back(va[i]);
return ans;
}
for(int i=0,l,r; i<n; i++)
{
if(vb.start<=va[i].end)
{
if(vb.end<va[i].start)
{
ans.push_back(vb);
while(i<n) ans.push_back(va[i++]);
}
else
{
l=min(vb.start, va[i].start);
r=max(vb.end, va[i].end);
for(int j=i,ff=1; j<=n; j++)
if(j==n)
{
if(!ff) break;
tmp.start = l;
tmp.end = r;
ans.push_back(tmp);
}
else if(vb.end>=va[j].start)
r=max(r, va[j].end);
else
{
if(ff)
{
tmp.start = l;
tmp.end = r;
ans.push_back(tmp);
ff = 0;
}
ans.push_back(va[j]);
}
}
return ans;
}
ans.push_back(va[i]);
}


}
};