Detailed C++ Explanation with best Time complexity
First Thoughts on the ProblemOn first glance it feels like a binary search or two pointers solution like part 2 of the problem, but here we can choose any queri
#  First Thoughts on the Problem
On first glance it feels like a binary search or two pointers solution like part 2 of the problem, but here we can choose any queries. For example, In part 2 if i have to choose 4 queries i can check using binary search as they would be the first 4 queries, but here i can choose any 4 queries and i just have to minimize the number of queries used to convert the array into a zero array. So we would indded go into a greedy direction here. Let's see how....

# Recommendation

Before proceeding: Highly recommend solving the part 2 of this problem in the optimal way using 2 pointers.. else this explanation would be tough to take.
Also Highly recommend having a pen and copy while understanding the problem.. and doing dry run along with the explanation

# Intution

See first thing to observe is that to bring a value down to 0 in the given array, would need that index to be a part of atleast 
nums[i] queries because each query can atmost take the value down by 1. Now if i want to choose which query should be the one taking the value down, i would obviously choose the one whose r(or ending index) is the farthest to the right as this will help in taking the values lying further ahead to 0.
So that was the greedy intution for the problem..

# Detailed Approach

***Step 1:*** First we create the difference array which we create to mark the queries. i.e if a query come with (l,r), we mark dif[l]++ and dif[r+1]--; This indicates that the values from l to r has been increased by 1 and to nullify the effect on further numbers we place -1 on r+1. The size of this dif array will be (n+1);

***Step 2:*** We then sort our queries array on basis of left index because when we will iterate from left to right, we must know which are the queries that can be used now and in future..

***Step 3:*** We would need a priority_queue (or maxheap) to store the potential queries. Now why a maxheap?? Because since we always try to choose a query with the farthest right index and this farthest index can be given to us by the maxheap.

***Step 4:*** We iterate through the entire array. On reaching the index i, we will iterate through the queries array and all the queries which have their left index less than or equal to i become the potential candidates and so we store their right indices in our maxheap. We move j to prevent doing this again and again and prevent O(n^2);

***Step 5:*** The variable sum is keeping track of how many queries are currently active for the index we are at. When we reach a index dif[i] will be 0;
Now if the value of sum is less than nums[i], it means the index as not yet been covered fully. So we start taking the elements out from the maxheap and if the maxheap gets empty in the process ,we straightaway return -1(because we cant find enough queries to cover for this index). Also if the value of element coming out from the maxheap is less than the current index, we discard it as that means that the query's range has ended before this index only.
If we pick a query, we mark dif[current_index]++, as this will help increase value of sum+dif[i] and also mark dif[r+1]-- as when our sum crosses that index, it gets reduced by 1 and the calculationsgo ahead correctly.

***Step 6:*** After doing for the index, we add the value of dif[i] to sum,as this will help in the future iterations and if the length of my query finishes it will automatically get subtracted form the sum using the values to dif[r];

***Step 7:*** The final step is to just return queries.size()-cnt, where cnt tracks the minimum number of required queries and this will give the maximum queries that can be removed...



# Code
```cpp []
class Solution {
public:
    int maxRemoval(vector<int>& nums, vector<vector<int>>& q) {
        int n=nums.size();
        int sz=q.size();
        sort(q.begin(),q.end());
        vector<int>dif(n+1);
        int sum=0;
        int j=0;
        priority_queue<int>pq;
        int cnt=0;
        for(int i=0;i<n;i++){
            while(j<sz && q[j][0]<=i){
                pq.push(q[j][1]);
                j++;
            }
            while(sum+dif[i]<nums[i]){
                if(pq.empty()){
                    return -1;
                }
                int a=pq.top();
                pq.pop();
                if(a>=i){
                    dif[i]++;
                    dif[a+1]--;
                    cnt++;
                }
            }
            sum+=dif[i];
        }
        return sz-cnt;
    }
};
```
# Do Upvote and Comment down the suggestions to make the explanations better!!
['Array', 'Greedy', 'Sorting', 'Heap (Priority Queue)', 'Prefix Sum', 'C++']