python bisect, beat 82%, very similar to Calendar Three
\n\n\nimport bisect\nimport collections\n\nclass Solution(object):\n    def fallingSquares(self, positions):\n        """\n        :type positions: List[List[in
\n\n```\nimport bisect\nimport collections\n\nclass Solution(object):\n    def fallingSquares(self, positions):\n        """\n        :type positions: List[List[int]]\n        :rtype: List[int]\n        """\n        \n        max_height = collections.defaultdict(int)\n        square_endpoints = []\n        \n        ans_max = 0\n        ans = []\n        for square in positions:\n            left = square[0]\n            right = left + square[1]\n            \n            if left not in max_height:\n                bisect.insort(square_endpoints, left)\n            if right not in max_height:\n                bisect.insort(square_endpoints, right)\n            \n            left_idx = bisect.bisect_left(square_endpoints, left)\n            right_idx = bisect.bisect_left(square_endpoints, right)\n            \n            if left not in max_height:\n                if left_idx - 1 >= 0:                    \n                    max_height[left] = max_height[square_endpoints[left_idx-1]]\n                else:\n                    max_height[left] = 0\n            \n            if right not in max_height:\n                max_height[right] = max_height[square_endpoints[right_idx-1]]\n                \n            height = 0\n            for i in range(left_idx, right_idx):\n                height = max(max_height[square_endpoints[i]], height)\n            \n            for i in range(left_idx, right_idx):\n                max_height[square_endpoints[i]] = height + square[1]\n                        \n            ans_max = max(ans_max, max_height[left])\n            ans.append(ans_max)\n            \n        return ans\n\t\t```
[]