[699. Falling Squares] C++ AC with brief explanation
We should divide the whole interval of the positions into different pieces.  Because if we directly consider each whole interval, like:\n\nfor this test case:  
We should divide the whole interval of the positions into different pieces.  Because if we directly consider each whole interval, like:\n\nfor this test case:  [[50,47],[95,48],[88,77],[84,3],[53,87],[98,79],[88,28],[13,22],[53,73],[85,55]], when we add [84,3] into our graph, the heigh is changed from 47 to 50 only for the interval [84->87], not the whole interval.\nSo from this, I think we should divide the whole interval by each start point and end point.\n\nIn order to distinguish the start point and end point, I add 0.5 to the start point. So each time we add a new interval, we can easily find out all shorter intervals it affects. By finding out the largest height at the affected interval, we can figure out the new height for this interval and the new largest height for the whole graph.\n\n\n    class Solution {\n    public:\n    vector<int> fallingSquares(vector<pair<int, int>>& positions) {\n        if(positions.empty()) return {};\n        int n = positions.size();\n        vector<int> res;\n        vector<double> intervals;\n        for(auto p : positions){\n            intervals.push_back(p.first + 0.5);\n            intervals.push_back((p.first + p.second)*1.0);\n        }\n        sort(intervals.begin(), intervals.end());\n        unordered_map<string, int> mp;\n        vector<int> height(intervals.size(), 0);\n        for(int i = 0; i < intervals.size(); ++i){\n            mp[to_string(intervals[i])] = i;\n        }\n        int glb_max = 0;\n        for(int i = 0; i < n; ++i){\n            int left = mp[to_string(positions[i].first + 0.5)];\n            int right = mp[to_string(positions[i].first*1.0 + positions[i].second)];\n            int cur_max = *max_element(height.begin() + left, height.begin() + right + 1);\n            while(left <= right){\n                height[left++] = cur_max + positions[i].second;\n            }\n            glb_max = max(glb_max, cur_max + positions[i].second);\n            res.push_back(glb_max);\n        }\n        return res;\n    }\n    };
[]