LeetCode-56-Merge-Intervals

Given a collection of intervals, merge all overlapping intervals.
For example,

1
2
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

如例子中所示,每个数组的前后分别表示开始和结束,工作是合并有重叠的数组。例如,由于[1,3]和[2,6]有重叠,故直接改为[1,6]后输出。
想法还是比较简单的,因为输入的并不一定是给好的按照开始,所以需要先对输入以开始的值排序。首先在结果数组中写入第一个,只有遍历进行判断,分为两种情况:

  1. 如果某一interval的开始比结果数组中的结尾要大,显然不会有重叠,直接写入到结果数组中即可;
  2. 某一interval的开始比结果数组中的结尾要大,必然有重叠,此时还需要判断结束位置的大小。

代码如下:

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
/**
* 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> merge(vector<Interval>& intervals) {
vector<Interval> res;
if(intervals.size()<=0)
return res;
sort(intervals.begin(),intervals.end(),[](Interval a,Interval b){return a.start<b.start;});
res.push_back(intervals[0]);
for(int i=1;i<intervals.size();++i){
if(res.back().end<intervals[i].start) res.push_back(intervals[i]);
else{
res.back().end=max(res.back().end,intervals[i].end);
}
}
return res;
}
};

57-Insert-Interval

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.

题目改为向一个已经重叠的数组中加入新加入一个。需要做的是判断所处的位置,插入进去后还要删掉,值得注意的是这个删掉值的时候,vector的迭代器会发生变化,即有些会失效,所以最好的做法是,先插入,把需要的插入都插入之后再删除。

另外还有一个值得注意的是,排序搜索的谓语,使用的是a.end<b.start,而不是之前的a.start<b.start ,原因是需要找到一个范围,将newINterval夹在中间的一个范围。

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
/**
* 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) {
if(intervals.size()<=0){
intervals.push_back(newInterval);
return intervals;
}
auto range=equal_range(intervals.begin(),intervals.end(),newInterval,[](Interval a,Interval b){return a.end<b.start;});
auto iter1=range.first,iter2=range.second;
if(iter1==iter2)
intervals.insert(iter1,newInterval);
else{
iter2--;
iter2->start=min(newInterval.start,iter1->start);
iter2->end=max(newInterval.end,iter2->end);
intervals.erase(iter1,iter2);
}
return intervals;
}
};