https://leetcode.com/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int mx = 0;
        for (auto &x: intervals) mx = max(mx, x[1]);
        vector<int> lineswap(mx * 2 + 10, 0);
        for (auto &x: intervals) {
            lineswap[x[0] * 2] += 1;
            lineswap[x[1] * 2 + 1] -= 1;
        }
        for (int i = 1; i <= mx * 2 + 1; i++) {
            lineswap[i] += lineswap[i - 1];
        }
        vector<vector<int>> res;
        int r = 0;
        while (r <= mx * 2) {
            if (lineswap[r] == 0) {
                r++;
                continue;
            }
            int l = r;
            while (lineswap[r]) r++;
            res.push_back({l / 2, r / 2});
        }
        return res;
    }
};

Time Complexity: O(n)
Space: O(n)

這裡有一個小技巧，因為遇到 [[1, 2], [3, 4]] 時結果會是兩個沒有 overlapping ，但是基本的 linewape 方法會沒辦法檢測到這樣的情況。此時如果我們將數字放大兩倍就可以避免這個問題，也就是我們將拿到的 intervals 改成 [[2, 4], [6, 8]]，這樣就又可以愉快的使用 linewape 解決這題了。