# 56. 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]`.

## Thoughts

interval有时间先后顺序，根据start排序。遍历并当interval.start小于等于res.last.end时合并进res.last，否则插入到res。

## Code

```
/*
 * @lc app=leetcode id=56 lang=cpp
 *
 * [56] Merge Intervals
 */
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        if (intervals.size() == 0) return res;
        sort(intervals.begin(), intervals.end(), [](vector<int> &a, vector<int> &b) {
            return a[0] < b[0];
        });
        res.push_back({intervals[0][0], intervals[0][1]});
        for (int i = 1; i < intervals.size(); ++i) {
            auto &last = res[res.size() - 1];
            if (intervals[i][0] <= last[1]) {
                last[1] = max(last[1], intervals[i][1]);
            } else {
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};


```

## Analysis

排序耗时O(nlgn).
