LeetCode Merge Intervals

LeetCode 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].


给定一个区间数组,也就是数组中保存的是一个个的区间[s,t],要求把数组中所有有overlap的区间合并起来。

简单题,先给数组排个序,然后只要看相邻的两个区间是否有重复就好了。排序的规则是先比较start,如果start相等,再比较end。

其实这个区间完全可以用pair来存,但是题目用一个自定义的Interval结构体存储。有两种方法可以对自定义结构体(或类)排序,一是重载Interval的小于<比较运算符,这样就可以直接sort(vector.begin(),vector.end())了,但是这样改变了Interval;还有一种方法是不改变Interval,自定义一个comp比较函数,传递给sort算法的第三个参数。

代码如下:

bool comp(const Interval& i, const Interval& j) {
	return (i.start < j.start) || ((i.start == j.start) && (i.end < j.end));
}

class Solution {
public:
	vector<Interval> merge(vector<Interval>& intervals) {
		if (intervals.size() == 0)return vector<Interval>();
		sort(intervals.begin(), intervals.end(), comp);
		vector<Interval> ans = { intervals[0] };
		for (int i = 1; i < intervals.size(); ++i) {
			if (intervals[i].start <= ans.back().end) {
				ans.back().end = max(ans.back().end, intervals[i].end);
			}
			else {
				ans.push_back(intervals[i]);
			}
		}
		return ans;
	}
};

本代码提交AC,用时12MS。

One thought on “LeetCode Merge Intervals

  1. Pingback: LeetCode Insert Interval | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *