Easy | Logical Greedy | Sort + Priority Queue
Intuition\n Describe your first thoughts on how to solve this problem. \nIt\'s not necessary to process queries in the given order.\nSo, we can manipulate the q
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt\'s not necessary to process queries in the given order.\nSo, we can manipulate the queries ordering to our advantage.\nAt any given index, I am only interested in the queries that can help me to compute min queries needed to make that index\'s value 0.\nBasically, queries which have starting point as index+1 or more are of no use to me while dealing with value at the index.\n\nAlso, it is always always always advantageous to pick such a query (from the available pool of queries at that index) such that its ending point is the farthest. This is the greedy nature of the problem. Think why this would be the optimal everytime. (Spoiler - because in future you would potentially save some queries usage if you proceed like this.)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSort the queries.\nMaintain a max-heap of all the queries available till the index on which you are at currently. (MaxHeap\'s key would be the ending point of the query due to the above mentioned intuition) \n\nJust iterate through the nums array, index by index and keep count of used queries till this point. The maxHeap might also have some old queries which are of no use to us --> simply ignore and remove them whenver you encounter them as those queries can no longer help us in any way as their range doesn\'t cover the current index, we are on.\n\n**Note**\nAlso maintain the diff array to efficiently keep track of future indices which are covered when you decide to use a particular query.\nSo that, in future you do not waste queries on indices which were already covered by your used queries in the past.\n\n\n# Complexity\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {\n        sort(queries.begin(), queries.end());\n        priority_queue<array<int, 2>> maxHeap;\n        int nidx = 0, qidx = 0, used = 0, curr = 0;\n        vector<int> diff(int(nums.size())+1, 0);\n        while(nidx < nums.size()) {\n            curr += diff[nidx];\n            while(qidx < queries.size() && queries[qidx][0] <= nidx) {\n                maxHeap.push({queries[qidx][1], queries[qidx][0]});\n                qidx ++;\n            }\n            while(nums[nidx] > curr) {\n                if(!maxHeap.empty() && maxHeap.top()[1] <= nidx && maxHeap.top()[0] >= nidx) {\n                    curr ++;\n                    diff[maxHeap.top()[0] + 1] -= 1;\n                    used ++;\n                    maxHeap.pop();\n                }\n                else if(!maxHeap.empty()) {\n                    maxHeap.pop();\n                }\n                else return -1;\n            }\n            nidx ++;\n        }\n        return int(queries.size()) - used;\n    }\n};\n```
['Array', 'Greedy', 'Heap (Priority Queue)', 'C++']