56. Merge Intervals

problem description

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.

algorithm thought

两个间隔能合并，就是两个范围有重合。重合的话存在两种情况，第一种是左边重合，一种是右边重合。但是如果程序中同时考虑两个的话，情况会复杂很多。所以首先按照做范围排序，消除左边影响。然后一直看右边，如果当前interval与前一个interval重合，合并两个interval。然后继续看下一个，如果两个不重合，将当前interval push进vector，访问到下一个时，当前interval就是下一个interval

code

/**
 * 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:
    vector<Interval> merge(vector<Interval>& ins) {
    if (ins.empty()) return vector<Interval>{};
    vector<Interval> res;
    sort(ins.begin(), ins.end(), [](Interval a, Interval b){return a.start < b.start;});
    res.push_back(ins[0]);
    for (int i = 1; i < ins.size(); i++) {
        if (res.back().end < ins[i].start) res.push_back(ins[i]);
        else
            res.back().end = max(res.back().end, ins[i].end);
    }
    return res;
}
};

algorithm analysis

首先排序，时间复杂度O(nlgn)。然后一个遍历数组，时间复杂度O(n)。最后时间复杂度O(nlgn)。这样看来，排序成了我们的瓶颈，但是也不能这么说，如果没有排序，时间复杂度至少是O(n²)