Python: priority queue and union find
Intuition\n Describe your first thoughts on how to solve this problem. \nGreedy approach made sense intuitively, so just make a min heap and poll the indices wi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nGreedy approach made sense intuitively, so just make a min heap and poll the indices with the lowest cash first. To make sure we can get $$k$$ houses without adjacent picks, we form a graph where adjacent visited houses are linked, and count the components. The max number of visits can then be calculated by $$\\Sigma_{i} (size(i) + 1)/2$$ where $$i$$ is a component. \n\n# Code\n```\nimport heapq\nfrom typing import List\n\nclass Solution:\n\n\n    def minCapability(self, nums: List[int], k: int) -> int:\n        pq = []\n\n        # union find \n        size = []\n        parent = []\n\n        #keep track of visited\n        visited = [False for _ in range(len(nums))]\n\n        for i in range(len(nums)):\n            heapq.heappush(pq, (nums[i], i))\n            parent.append(i)\n            size.append(1)\n\n\n        def find(i) -> int:\n            if parent[i] == i:\n                return i\n            parent[i] = find(parent[i])\n            return parent[i]\n\n        def union(i1, i2):\n            p1 = find(i1)\n            p2 = find(i2)\n            if p1 == p2:\n                return \n            \n            if size[p1] > size[p2]:\n                parent[p2] = p1\n                size[p1] += size[p2]\n            else:\n                parent[p1] = p2\n                size[p2] += size[p1]\n\n        cur = 0\n        change = -1\n\n        while (cur < k):\n            change, i = heapq.heappop(pq)\n            visited[i] = True\n            if i-1 >= 0 and visited[i-1]:\n                cur -= int((size[find(i-1)]+1)/2)\n                union(i-1, i)\n            if i+1 < len(size) and visited[i+1]:\n                cur -= int((size[find(i+1)]+1)/2)\n                union(i+1, i) \n            cur += int((size[find(i)]+1)/2)\n\n        return change\n\n```
['Python3']