Concise Heap Solution in Python3 with Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nTry to construct the answer by using as few (l, r) elements as possible.\n\nMaintain th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTry to construct the answer by using as few `(l, r)` elements as possible.\n\nMaintain three priority queues, Q, A, and W as follows:\n\n- In Q, all the input `(l, r)` are sorted by `l`.\nFor position `i`, we move all the available elements from Q to A.\n- A is another queue of `(l, r)` sorted by `r` in the descending order. \nA contains the available elements ready to select. If we want to pick up an element, it is better to the most capalable one, which is the one with the largest `r` in A. For this reason, A is sorted by `r` in the descending order. \n- The last queue W contains the currently working elements. When we move to position `i`, the first step is to retire the elements that does not work for `i`. In other words, the elements with $r < i$ should be discarded. For this reason, W is sorted by `r` in the ascending order. Then, we check the working elements is enough to cover `nums[i]`. If `nums[i] > len(W)`, we need pick up more elements from A to W. The answer will be -1 if no valid elements (i.e., $l \\le i \\le r$) can be chosen from A.  \n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nQ should support efficient `pop()`. Thus I implement Q as a deque that initialized by `nums` sorted by `l`. A and W require both `pop()` and `push()` operations, I employ heap for both. \n      \n# Complexity\n- Time complexity: The overall complexity is $O(N + M \\log M)$, where $N$ is the length of `nums` and $M$ is the length of `queries`.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:\n        q = deque(sorted(queries))\n        available = []\n        working = []\n        for i in range(len(nums)):\n            while q and q[0][0] <= i:\n                heappush(available, -q.popleft()[1])\n            while working and working[0] < i:\n                heappop(working)\n            while nums[i] > len(working):\n                if available and -available[0] >= i:\n                    heappush(working, -heappop(available))\n                else:\n                    return -1\n        return len(available)\n```\n\nThank zsq007 for his/her enlightenment suggestion to improve my code.
['Heap (Priority Queue)', 'Python3']