题解 | #不重叠的身高#

#include <map>
#include <vector>
#include <algorithm>

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param intervals int整型vector<vector<>>
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > mergeAnimalRanges(vector<vector<int> >& intervals) {
        // write code here
        for (auto invM : intervals) {
            // 左侧无区间，右侧无区间
            if (buffer.empty()) {
                buffer[invM[0]] = invM;
                continue;
            }
            auto itR = buffer.lower_bound(invM[0]);
            // 左侧有区间，右侧无区间
            if (itR == buffer.end()) {
                auto itL = itR;
                --itL;
                auto invL = itL->second;
                if (canMerge(invL, invM)) { // 可以合并，则调整待插入区间
                    buffer.erase(itL);
                    invM = Merge(invL, invM);
                }
                buffer[invM[0]] = invM;
                continue;
            }
            // 左侧无区间，右侧有区间
            if (itR == buffer.begin()) {
                auto invR = itR->second;
                if (canMerge(invM, invR)) {  // 可以合并，则调整待插入区间
                    buffer.erase(itR);
                    invM = Merge(invM, invR);
                }
                buffer[invM[0]] = invM;
                continue;
            }
            // 左侧有区间，右侧有区间
            auto itL = itR;
            itL--;
            auto invL = itL->second;
            auto invR = itR->second;

            if (canMerge(invL, invM) && canMerge(invM, invL)) { // 将三者合并
                buffer.erase(itL);
                buffer.erase(itR);
                invM = Merge(invL, invM, invR);
            } else if (canMerge(invL, invM)) { // 与左侧合并
                buffer.erase(itL);
                invM = Merge(invL, invM);
            } else if (canMerge(invM, invR)) { // 与右侧合并
                buffer.erase(itR);
                invM = Merge(invM, invR);
            }
            buffer[invM[0]] = invM;

        }
        vector<vector<int> > ret = vector<vector<int> >();
        for (auto kv : buffer) {
            ret.push_back(kv.second);
        }
        return ret;
    }

    map<int, vector<int> > buffer = map<int, vector<int> >();

    // 两个区间是否可以合并
    bool canMerge(vector<int>& l, vector<int>& r) {
        return l[0] <= r[1] && r[0] <= l[1];
    }

    // 合并区间
    vector<int> Merge(vector<int> l, vector<int> r) {
        return {min(l[0], r[0]), max(l[1], r[1])};
    }

    // 合并区间
    vector<int> Merge(vector<int> l, vector<int> m, vector<int> r) {
        return Merge(Merge(l, m), r);
    }

};