0056. 合并区间 [Medium] [Merge Intervals].md

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.

---

题目：合并重叠的interval。

思路：首先按照$x_{start}$进行排序，不要按照$x_{end}$排序。取排序后的第一个intervals[0]对应的end作为分界点，如果第二个intervals[1]->start大于等于intervals[0]->end，说明这两个存在重叠，更新end为两者中的最大值，直到不重叠，保存该结果，重复以上步骤。

工程代码下载

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        sort(intervals.begin(), intervals.end(), cmp);

        for(auto vec : intervals){
            int n = res.size();
            if(res.empty() || res[n-1][1] < vec[0])
                res.push_back(vec);
            else
                res[n-1][1] = max(res[n-1][1], vec[1]);
        }

        return res;
    }
private:
    static bool cmp(vector<int>& a, vector<int>& b){
        return a[0] < b[0];
    }
};

旧代码

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        sort(intervals.begin(), intervals.end(), cmp);

        int n = intervals.size(), i = 0;
        while(i < n){
            int start = intervals[i][0];
            int end = intervals[i][1];

            while(++i < n && end >= intervals[i][0]){
                end = max(end, intervals[i][1]);
            }
            res.push_back(vector<int>{start, end});
        }

        return res;
    }
private:
    static bool cmp(vector<int>& a, vector<int>& b){
        return a[0] < b[0];
    }
};

测试用例：

[[2,3],[4,5],[6,7],[8,9],[1,10]]

[[1,4],[2,3]]

Solution给出的解法https://leetcode.com/problems/merge-intervals/solution/

class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda x: x.start)

        merged = []
        for interval in intervals:
            # if the list of merged intervals is empty or if the current
            # interval does not overlap with the previous, simply append it.
            if not merged or merged[-1].end < interval.start:
                merged.append(interval)
            else:
            # otherwise, there is overlap, so we merge the current and previous
            # intervals.
                merged[-1].end = max(merged[-1].end, interval.end)

        return merged