題目： LeetCode - 56. Merge Intervals

題目說明

給一個代表區間的陣列，要求將有重疊的區間合併。

解題思路

先將區間依照起始點排序，接著遍歷區間，若是第一個區間或是區間的起始點大於上個區間的結尾點，表示兩者沒有重疊，直接存入 res，否則更新上個區間的結尾點即可將兩個區間合併。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals)
    {
        sort(intervals.begin(), intervals.end(), [](auto& l, auto& r) { return l[0] < r[0]; });
        vector<vector<int>> res;
        for(auto& interval : intervals)
        {
            if(res.empty() || interval[0] > res.back()[1]) res.emplace_back(interval);
            else res.back()[1] = max(res.back()[1], interval[1]);
        }
        return res;
    }
};