Problem intuition explained, with step by step breakdown C++| Greedy | multiset
Tricks\nFix current index at one end and think either about indices in front or indices behind it.\nThis approach will help us maximise answer in one direction.
# Tricks\nFix current index at one end and think either about indices in front or indices behind it.\nThis approach will help us maximise answer in one direction.\n\nEg if we want to maximise impact on future choices, we assume all indices before current index are taken care of.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nselect 0th index,\nselect all queries applicable on 0th index.\n--> few of these queries will be chosen to make nums[0] == 0\n--> since we are sure all queries start with 0, we have no use for starting index of queries\n--> store all applicable queries end index in **validQ**\n\nnow out of **validQ** we need to choose endIndex,\nlets store these chosen end indices in **activeQ**\n\n--> We want to choose such end indices from validQ which covers maximum possible upcoming indices.\n-->This is because we want to use up lesser queries to make upcoming indices 0. \n\nTherefore validQ needs to be sorted in descending order, so that farthest end index is chosen first. Hence multiset sorted in decending order.\n\nchoose top "nums[0]" values from **activeQ** and transfer to **validQ** and remove chosen values from activeQ.\nnote:\n--> if "nums[0]" values are not available in activeQ means we cannot reduces nums[0] to 0.\n\n\n--> nums[0] is now 0 : YAY!!\n\n\nwe have chosen indices and stored **validQ** with criteria to reuse them for the next nums elements, \nbut few of them are not valid as their query range ended at 0th index,\ntherefore we remove those **validQ** entries. \nwe use ascending order multiset to optimise this removal operation\n\nmove to next index:\nperform above operations for nums[1],\nwe dont worry about nums[0] as we are sure that it is 0.\n\n\n\n\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n\n    int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {\n\n        sort(queries.begin(), queries.end());\n        int j = 0;\n        multiset<int, greater<>> activeQ;\n        multiset<int> validQ;\n        int usedCount = 0;\n\n\n        for(int i=0; i<nums.size(); i++){\n\n            while(j<queries.size() and queries[j][0] == i){\n                activeQ.insert(queries[j][1]);\n                j++;\n            }\n        \n            nums[i]-=validQ.size();\n            \n            \n            while(nums[i]>0 and !activeQ.empty() and *activeQ.begin() >= i){\n             \n                validQ.insert(*activeQ.begin());\n                activeQ.erase(activeQ.begin());\n                \n                nums[i]--;\n                usedCount++;\n\n            }\n            \n            if(nums[i]>0){\n                return -1;\n            }\n\n            while(!validQ.empty() && (*validQ.begin() == i)){\n                validQ.erase(validQ.begin());\n            }\n\n        }\n\n        return queries.size() - usedCount;\n\n    }\n};\n```
['Greedy', 'Heap (Priority Queue)', 'C++']