56. Merge Intervals

https://leetcode.com/problems/merge-intervals/description/

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).