leetcode 56. Merge Intervals (medium)

先排序，再按照规则遍历intervals逐个插入到结果中。

以下情况则直接插入：

1. invals[i].second < invals[i+1].first前后两个范围无交叉
2. 第一次插入到结果

因为排序过，所以左边界一定是无需修改的。以下情况修改右边界：

1. invals[i].second >= invals[i+1].first 前后两个范围有交叉，同时invals[i].second < invals[i+1].second

class Solution
{
    
public:static bool cmp(const vector<int> &a, const vector<int> &b){
    if (a[0] == b[0])return a[1] < b[1];elsereturn a[0] < b[0];}vector<vector<int>> merge(vector<vector<int>> &inVals){
    sort(inVals.begin(), inVals.end(), cmp);vector<vector<int>> res;for (auto inv : inVals){
    if (res.empty() || res.back()[1] < inv[0]){
    res.push_back(inv);}else{
    res.back()[1] = max(res.back()[1], inv[1]);}}return res;}
};