# 56 - Merge Intervals

解法一 - Sorting(vector 版本)

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size() < 2) {
            return intervals;
        }

        // Sort the intervals by the start time
        sort(intervals.begin(), intervals.end(), 
             [](const vector<int>& i1, const vector<int>& i2) {
                return i1[0] < i2[0];
        });

        // Keep merging them
        vector<vector<int>> mergedIntervals;
        mergedIntervals.push_back(intervals[0]);
        for(int i = 1; i < intervals.size(); ++i) {
            if( mergedIntervals.back()[1] < intervals[i][0] ) {
                mergedIntervals.push_back(intervals[i]);
            }
            else {
                mergedIntervals.back()[1] = max(mergedIntervals.back()[1], intervals[i][1]);
            }
        }

        return mergedIntervals;
    }
};