LeetCode 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 considerred overlapping.
解析：
给定一组区间，让我们合并区间。即两个区间中有重叠的部分合并为一个区间。
首先根据区间的起始位置进行排序，因为输入是一个结构体，所以需要自己定义排序函数。排序完成之后，我们维护一个[start, end]数组，初始未排序后第一个元素，即start最小的元素，然后从第二个开始，依次查看当前的区间如果在[start,end]之间则进行合并，选择end为最远的那个；否则，无法合并，将[start,end]加入结果集中，并更新[start,end]数值。

class Solution {
public:
    static bool my_sort(vector<int>& a, vector<int>& b)
    {
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        int len = intervals.size();
        if(len == 0)
            return result;
        std::sort(intervals.begin(), intervals.end(), my_sort);
        int begin = intervals[0][0];
        int end = intervals[0][1];
        for(int i =1; i < len; i++)
        {
            if(intervals[i][0] <= end)
            {
                end = max(end, intervals[i][1]);
            }else
            {
                result.push_back({begin, end});
                begin = intervals[i][0];
                end = intervals[i][1];
            }
        }
        result.push_back({begin, end});
        return result;
    }
};

[/cc] 运行结果如下：
参考：
https://blog.csdn.net/MebiuW/article/details/51255535</vector</vector</vector</j.start);>