1 Max-Heap + Sorting (N log Q) simplest explanation !
Intuitionfor any index i in nums we need to consider the query that has longest impact i + right is maxed out so more numbers ca benfit from that query being us
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nfor any index i in nums we need to consider the query that has longest impact i + right is maxed out so more numbers ca benfit from that query being used\n# Approach\n 1) sorted all the queries to effectily pick and add to valid queries list.\n 2) preSum arrary to track at with point previouly applied queries are going to be applicable.\n\n 3) for each index i in nums we add all the valid queries to the heap. we only add the right bound and add it with * -1 as we are using min heap as max heap.\n 4) if the current index needs to be adjusted using queries we pick queries one by one and increment the used queries. at times the queires could be invalid when the right bound is < than current i. this happens as we are not cleaning the heap with the old invalid queries.\n 5) we return the count of queries - usedqueires to get the count of removable queries.\n<!-- Describe your approach to solving the problem. -->\n\n\n\n# Complexity\n- Time complexity: N log Q (we do it N times & loq Q for heap ops)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: N + Q\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n\n\nCurious to know if there is any way to remove the invalid queries efficently as this will improve the heap operations performance.\n\n\n# Code\n```python3 []\nclass Solution:\n    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:\n        queries.sort(key = lambda x: x[0])\n        preSum = [0] * (len(nums)+1)\n\n        validQueries = []\n        k = 0\n        currentSum = 0\n        userQueries = 0\n\n        for i in range(len(nums)):\n            while k < len(queries) and queries[k][0] <= i:\n                heapq.heappush(validQueries, -queries[k][1])\n                k+=1\n\n            while currentSum + preSum[i] < nums[i]:\n                if len(validQueries) == 0 or -validQueries[0] < i:\n                    return -1\n            \n                right = heapq.heappop(validQueries)\n                right = -right\n\n                preSum[i] += 1\n                preSum[right + 1] -= 1\n                userQueries += 1\n\n            currentSum += preSum[i]\n        return len(queries) - userQueries\n\n```
['Python3']