题解 | #不重叠的身高#
不重叠的身高
https://www.nowcoder.com/practice/b11cb8804f5d4eb3b221a019efe3ad5f
#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); } };