Heap+ Queue
Intuition\n Describe your first thoughts on how to solve this problem. \n- assume  m is the number of queries\n- sort the queries based on l (from [l,r]) and pr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- assume  `m` is the number of queries\n- sort the queries based on l (from `[l,r]`) and present it as a queue\n- for all those l\'s within a particular idx `i` remove them and put their `r` in a max heap\n- filtering- remove all those `r` which don\'t contain i (`r < i`)\n- put elements from max-heap to the selected, till we have the required count\n    - exception: if we find insufficient `r`\'s, return -1\n- answer is `m` - ans\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n`O((m+n)logm)` where `m` is the number of queries and `n` is the number of elements in `nums`\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n`O(m)` where `m` is the number of queries\n\n# Code\n```python3 []\nfrom collections import deque\nclass Solution:\n    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:\n        # Maintain a queue of sorted queries based on l from [l,r]\n        q= deque(sorted(queries))\n        # list to maintain max heap\n        h = []\n        selected =[]\n        ans = 0\n        # print(q)\n        for i in range(len(nums)):\n            # First pull out those queries for which l <= i \n            # and put it\'s r into max-heap\n            while q and q[0][0] <= i:\n                heapq.heappush(h,-q.popleft()[1])\n\n            # Before consideration, remove those r\'s from\n            # selected array which are less than i ( outside the range)\n            while selected and selected[0]<i:\n                heapq.heappop(selected)\n            \n            # the number of r\'s in selected are now greater\n            # than i, signifying possibility of using those\n\n            # Now you can select the largest r\'s from max-heap\n            # to be put into selected, in the middle if we find ineligible\n            # r, return -1\n            while nums[i] > len(selected):\n                if h and -h[0] >= i:\n                    # print(-h[0],i)\n                    heapq.heappush(selected,-heapq.heappop(h))\n                    \n                    ans += 1\n                else:\n                    return -1\n        # ans represents minimum number of queries\n        return len(queries)-ans\n\n        \n```
['Python3']