56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

---

给定一个区间数组，也就是数组中保存的是一个个的区间[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。

二刷。想到用栈来合并区间，代码如下：

class Solution {
public:
	bool IsOverlap(const pair<int, int>& interval1, const pair<int, int>& interval2) {
		return interval1.second >= interval2.first;
	}
	vector<vector<int>> merge(vector<vector<int>>& intervals) {
		vector<pair<int, int>> intervals2;
		for (int i = 0; i < intervals.size(); ++i) {
			intervals2.push_back(make_pair(intervals[i][0], intervals[i][1]));
		}
		sort(intervals2.begin(), intervals2.end());
		vector<vector<int>> ans;
		stack<pair<int, int>> stk;
		for (int i = 0; i < intervals2.size(); ++i) {
			if (stk.empty()) {
				stk.push(intervals2[i]);
			}
			else {
				pair<int, int> top = stk.top();
				stk.pop();
				if (IsOverlap(top, intervals2[i])) {
					stk.push(make_pair(top.first, max(top.second, intervals2[i].second)));
				}
				else {
					ans.push_back({ top.first,top.second });
					stk.push({ intervals2[i].first,intervals2[i].second });
				}
			}
		}
		if (!stk.empty())ans.push_back({ stk.top().first,stk.top().second });
		return ans;
	}
};

本代码提交AC，用时24MS，效率不如第一种方法高。