关关的刷题日记99 – Leetcode 56. Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
题目的意思是给出一个区间集合,让我们合并所有重叠区间。
首先我们要对集合进行从小到大排序,因为区间是自己定义的数据结构,所以我们要自己定义排序函数。需要注意的是自定义排序时,sort中的比较函数compare要声明为静态成员函数或全局函数,不能作为普通成员函数,否则会报错:invalid use of non-static member function。 排好序之后遍历集合的每一个区间,如果后面的区间的左端点小于等于左边的区间的右端点,那么这两个区间就可以合并。
/ **
*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:
static
bool
cmp(Interval
a, Interval
b)
{
if (a.start != b.start)
return a.start < b.start;
else
return a.end < b.end;
}
vector < Interval > merge(vector < Interval > & intervals) {
vector < Interval > output;
if (intervals.empty())
return intervals;
sort(intervals.begin(), intervals.end(), cmp);
output.push_back(intervals[0]);
for (int i=1; i < intervals.size();++i)
{
if (intervals[i].start <= output.back().end)
output.back().end = max(intervals[i].end, output.back().end);
else
output.push_back(intervals[i]);
}
return output;
}
};
人生易老,唯有陪伴最长情,加油!
以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)。