C++ O(nlog(n)) solution beats 95%
Hi, this is my concise and fast C++ solution based on set. We use this set to store the height of each interval and update iteratively.\n\n\nvector<int> falling
Hi, this is my concise and fast C++ solution based on `set`. We use this set to store the height of each interval and update iteratively.\n\n```\nvector<int> fallingSquares(vector<vector<int>>& positions) {\n\tvector<int> ret;\n\tmap<int, int> r2h; // right to height\n\tr2h[INT_MAX] = 0;\n\tint maxh = 0;\n\tfor(auto &position: positions){\n\t\tint l=position[0], d=position[1];\n\t\tint r = l + d;\n\t\tauto iter = r2h.upper_bound(l);  // O(logn) operation for set\n\t\tint wh = iter->second;\n\t\tif(!r2h.count(l)) r2h[l] = wh;\n\t\twhile(iter->first<r){\n\t\t\t// Erase the interval that will be overlapped. Each interval will be erased at most once.\n\t\t\titer = r2h.erase(iter);\n\t\t\twh = max(wh, iter->second);\n\t\t}\n\t\t// update the height of current interval\n\t\tr2h[r] = wh + d;\n\t\tmaxh = max(maxh, wh+d);\n\t\tret.push_back(maxh);\n\t}\n\treturn ret;\n}\n```
[]