Python3 with clear explanation
Intuitionrefer to the code comments for more info.Intuition is to maintain a list of queries that covers each index. By this, I mean to say, you will need to kn
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nrefer to the code comments for more info.\n\nIntuition is to maintain a list of queries that covers each index. By this, I mean to say, you will need to know the number of queries for which l <= i <= r. But We also needed to minimize the number of queries used to reduce arr[i] to 0. So, the best way is to choose the queries greedily spanning the largest (those having highest r) until you can reduce arr[i] to 0. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nFor each index i, we will start adding queries with l <= i and then choose those with r >= i starting from the largest r. Once we reach number of queries == nums[i] which means we can reduce nums[i] to 0 with the chosen queries we can move to next index.\n\nTo process queries for current index, use a queue with the queries sorted in ascending order of l to make it easy to pop.\nMaintain a maxheap valid, which will be used to choose queries with the highest r among the queries which have l <=i <= r. \nWe also need a minheap active, which keeps a count of the current queries for index i. We need this because we can\'t just remove the query from valid, it can be used for next indexes (i+1, i+2, so on) as well. And a min heap because we want to remove the queries which have r<i easily.\n\nNow, for each index i:\n- add queries from queue to valid if l <= i.\n- remove queries from active if r < i.\n- keep pushing into active until we find nums[i] queries. if we can\'t return -1\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N + Mlog(M)), m is the length of queries.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(M)\n\n# Code\n```python3 []\nclass Solution:\n    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:\n        q = deque(sorted(queries)) #process queries one by one with the smallest l\n        valid = [] #stores valid queries which have l<i for each index i and in maxheap. We use a maxheap because we need to choose the biggest range of valid query to maximize the number of unnecessary queries.\n        active = [] #stores the chosen queries from valid queries used for each index i to reduce them to zero. We use minheap for this because we want to remove the inactive queries which have r < i (these were already used for previous indexes and are now invalid)\n\n#so basically for each index we maintain the number of queries that cover this index and to do it greedily we needed to use heaps.\n\n        for i in range(len(nums)):\n            #add valid queries to heap if l < i\n            while q and q[0][0] <=i:\n                heappush(valid, -q.popleft()[1])\n            #remove inactive queries which have r < i\n            while active and active[0] < i:\n                heappop(active)\n            #now choose queries in valid have r > i from the biggest r\n            while nums[i] > len(active):\n                #if there are no more valid(l<i) or the biggest r valid is < i, we dont have enough queries to reduce  nums[i] to zero.\n                #since each query reduces nums[i] by 1. we need len(active) to be equal to nums[i]\n                if not valid or -valid[0] < i:\n                    return -1\n                heappush(active, -heappop(valid))\n        #return the number of unchosen queries\n        return len(valid)\n```
['Python3']