56. Merge Intervals

這個題目我們首先要先對每個vector的首位數進行排列

接著我們把第一個vector先丟進答案裡

第二個vector我們有以下三種情況

1. a[1, 3] b[2, 4]
2. a[1, 3] b[4, 6]
3. a[1, 4] b[2, 3]

case 1當我們發現a[1] > b[0]時, 我們就知道overlap了

所以我們可以直接把a[1]換成b[1], 但是這邊有一種特殊的case

那就是case3

如果我們直接換掉, 反而換到小的, 所以在這邊我們要在比一次兩邊的大小

如果是a[1] < b[0], 就中斷了 我們就把b給加到答案裡

class Solution {
  public:
    static bool s(vector<int> &a, vector<int> &b) { return a[0] < b[0]; }
    vector<vector<int>> merge(vector<vector<int>> &intervals) {
        if (intervals.size() == 0) {
            return vector<vector<int>>{};
        }
        sort(intervals.begin(), intervals.end(), s);
        vector<vector<int>> res{intervals[0]};
        for (int i = 1; i < intervals.size(); i++) {
            if (res.back()[1] < intervals[i][0]){
                res.push_back(intervals[i]);
            }else{
                res.back()[1] = max(intervals[i][1], res.back()[1]);
            }
        }
        return res;
    }
};