56.合并区间.md

// 复习
// 排序+for()遍历处理

// 此题在我看来较难想到，属于要提前排序的题，这点很关键，应该在阅读题意时有所感觉，理由如下：
// 1）数组，且和比大小有关。
// 2）对于这种数组，示例1、2都已经排序过了，如果不排序，看起来一定会更麻烦，应该感觉到需要排序。
// 3）画出2个区间，进行思考，如果排序，那其实情况数大大减小，因为只是对左元素排序，即intervals[i][0]，排
// 完后会发现，[1 a][1 b]或[1 a][2 b]，那就是后面的组的左元素和前面的组的左元素相比，要么相等，要么大于，
// 不会小于。

// 这有什么用？画图就会非常清楚，对于两个区间，无非就是最后合并成一个区间连续，或者还是两个区间不连续，
// 两种情况。由于上述排序，所以导致不管是合成一个，还是保持两个，其最左元素已经确定，那就是前组的左元素。
// 其实此时，一共就两种情况了：
// [1 3] [4 6]那就是保持两个，不连续。结果[1 3] [4 6]。
// [1 3] [2 6]那就是保持一个，连续。结果[1 6]。
// 其他的情况，说得再多，无非也就是连续或不连续。首先将第一个区间[1 3]加入结果result，然后for遍历从i=1处理
// 循环，遇到[2 6]，因为3>=2，所以连续；遇到[4 6]，因为3<4，所以不连续。对于不连续的情况，直接将第二个区间
// 加入结果result；对于连续的情况，则只有一个区间，左元素一定是1（前面已经提到过，前组的左元素），右元素则
// 是前组的右元素和后组的右元素取大的即可。用区间画图，会更加清晰！

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 排序是关键，比大小，搞成升序数组先，减少需要考虑的情况数。
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> result;
        // 遍历for装结果用，再复杂的问题，到这也就是遍历for，result遇到每个i组，要么装新的，要么合并last。
        result.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            auto last = result.back();
            // 排序后，由于后组左不可能在前组左的左边，所以下限就是前组左！
            // 排序后，只需比前组右&后组左，就2种情况，要么连续，要么不连续！
            if (last[1] < intervals[i][0]) {
                // 不连续，则[1 3] [4 6]那就是保持两个，不连续。结果[1 3] [4 6]。
                result.push_back(intervals[i]);
            } else {
                int last_left = last[0];
                int last_right = last[1];
                result.pop_back();
                // 连续，则[1 3] [2 6]那就是保持一个，连续。结果[1 6]。
                result.push_back({last_left, max(last_right, intervals[i][1])});
            }
        }

        return result;
    }
};