My Solution for #3161 Block Placement Queries Problem
Intuition\nMy first thought was to devise a method to efficiently manage the obstacles on the number line and quickly determine if a block of a given size can b
# Intuition\nMy first thought was to devise a method to efficiently manage the obstacles on the number line and quickly determine if a block of a given size can be placed without intersecting any obstacles. However, since we are dealing with an infinite number line, we need to come up with a strategy to handle dynamic updates to the obstacles and efficiently answer queries about block placement within specified ranges. This would likely involve using appropriate data structures and algorithms to keep track of obstacles and gaps between them, allowing us to quickly determine the feasibility of block placement for each query.\n\n# Approach\nI used a combination of data structures and algorithms to efficiently manage obstacles on the number line and answer queries about block placement. The key components of our approach are:\n\nData Structures:\nI used a SortedSet to maintain the positions of obstacles on the number line. This data structure allows efficient insertion, deletion, and searching operations while keeping the obstacles sorted.\n\nAdditionally, we need to use another SortedSet to keep track of gaps between consecutive obstacles. This will help us quickly determine the largest available gap where a block can be placed.\n\nHandling Queries:\nFor queries of type 1 ([1, x]), which involve adding obstacles, we insert the obstacle position into the SortedSet of obstacles and update the set of gaps accordingly.\nFor queries of type 2 ([2, x, sz]), which involve checking block placement, we will search for a gap of at least sz units within the specified range [0, x]. This can be done by examining the gaps stored in the SortedSet of gaps.\n\nEfficient Updates and Searches:\nInsertion and deletion operations on a SortedSet have logarithmic time complexity, allowing us to efficiently maintain sorted order.\nBy using binary search and efficient algorithms to find and update the necessary gaps when adding new obstacles, we can achieve the desired performance.\n\n# Complexity\n- Time complexity:\nWhen inserting an obstacle into the SortedSet, the time complexity is \uD835\uDC42 (log \uD835\uDC5B), where \uD835\uDC5B is the number of obstacles currently present. This is because SortedSet maintains its elements in sorted order, allowing for efficient insertion using techniques like binary search. For each query of type 2, we need to search for a gap of at least sz units within the specified range. This search operation also has a time complexity of \uD835\uDC42 (logn) since it involves searching through the SortedSet of gaps, which is sorted based on gap size.\n\n- Space complexity:\nThe space complexity for storing obstacles is \uD835\uDC42 (n), where n is the number of obstacles. Each obstacle is stored in the SortedSet, which requires space proportional to the number of obstacles.Similarly, the space complexity for storing gaps is also O(n). Although the number of gaps might be smaller than the number of obstacles, in the worst case where there is a gap between every pair of obstacles, the number of gaps would be \nO(n).\n\n# Code\n```\nfrom sortedcontainers import SortedSet\nfrom typing import List\n\nclass Solution:\n    def getResults(self, queries: List[List[int]]) -> List[bool]:\n        results = []\n        obstacles = SortedSet([0, 10**12])\n        gaps = SortedSet([(10**12, 10**12)])\n\n        for query in queries:\n            if query[0] == 1:\n                # Add obstacle\n                x = query[1]\n                it1 = obstacles.bisect_right(x)\n                it2 = it1 - 1\n                prev_obstacle = obstacles[it2]\n                next_obstacle = obstacles[it1]\n\n                # Remove old gap and add new gaps\n                gaps.discard((next_obstacle - prev_obstacle, next_obstacle))\n                gaps.add((x - prev_obstacle, x))\n                gaps.add((next_obstacle - x, next_obstacle))\n\n                obstacles.add(x)\n            else:\n                # Check for block placement\n                x = query[1]\n                sz = query[2]\n                can_place = False\n\n                it = gaps.bisect_left((sz, 0))\n                while it < len(gaps):\n                    gap_size, obstacle = gaps[it]\n                    it2 = obstacles.index(obstacle) - 1\n                    prev_obstacle = obstacles[it2]\n\n                    if prev_obstacle + sz <= x:\n                        can_place = True\n                        break\n                    it += 1\n\n                results.append(can_place)\n\n        return results\n\n```
['Python3']