C++, map with explanation, O(nlogn) solution 36ms
The idea is to store all non-overlapping intervals in a tree map, and to update the new height while adding new intervals into the map.\nThe interval is represe
The idea is to store all non-overlapping intervals in a tree map, and to update the new height while adding new intervals into the map.\nThe interval is represented by left bound l, right bound r, and height h. The format in the map is \n'''\ninvals[l] = {r, h};\n'''\nThe number of intervals in the map is at most 2n. The run time for search, insert and erase is O(nlogn) when adding n intervals. The iteration from iterator low to up seems time consuming, but all those intervals will be deleted after the loop. So the run time for this part in total is O(2n) because there are at most 2n intervals to delete.\n\nFor some reasons possibly related to Leetcode platform, the low and up iterators part is very sensitive to revision. I have another version "equal" to this one, but it results in undefined behavior/random output.\n```\nclass Solution {\npublic:\n    vector<int> fallingSquares(vector<pair<int, int>>& positions) {\n        map<int, vector<int>> invals;\n        int n = positions.size();\n        vector<int> ht(n, 0);\n        int l = positions[0].first, h = positions[0].second;\n        ht[0] = h;\n        invals[l] = {l+h, h};\n        for (int i = 1; i < n; i++) {\n            int h = drop(invals, positions[i]);\n            ht[i] = max(h, ht[i-1]);\n        }\n        return ht;\n    }\nprivate:\n    // return the height of current square\n    int drop(map<int, vector<int>>& invals, pair<int, int>& square) {\n        int l = square.first, h = square.second, r = l+h, pre_ht = 0;\n        auto low = invals.lower_bound(l), up = invals.lower_bound(r);\n        // consider intervals in range [low-1, up) \n        if (low != invals.begin()) low--;\n        for (auto it = low; it != up; it++) \n            if (it->second[0] > l) pre_ht = max(pre_ht, it->second[1]);\n        // erase overlapping intervals, add current interval and update the interval at low and up-1\n        int l1 = low->first, r1 = low->second[0], h1 = low->second[1], r2 = 0, h2 = 0;\n        if (up != invals.begin()) {\n            up--;\n            r2 = up->second[0];\n            h2 = up->second[1];\n            up++;\n        }\n        invals.erase(low, up);\n        invals[l] = {r, pre_ht+h};\n        if (l1 < l) invals[l1] = {min(l, r1), h1};\n        if (r2 > r) invals[r] = {r2, h2};\n        return pre_ht+h;\n    }\n};\n```
[]