Heap with Linesweep Solution (With Complete Intuition, Approach and Explanation!!!)
IntuitionWe have to greedily find which queries can be used.
If there are multiple queries which can be used, the best one to be used would be the one which can
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
We have to greedily find which queries can be used.
If there are multiple queries which can be used, the best one to be used would be the one which can add values to a larger length of array (query having q[1] larger at same starting point)

# Approach
<!-- Describe your approach to solving the problem. -->
To employ such format, we push all the queries in the queue, sorting them by their first index.
Whenever we are at an index, we push all the queries that **can be used for current index** in a heap, sorting them by ending index in reverse. Hence, if we have 2 queries (0,4) and (0,6), we would employ (0,6) first so that our query covers a larger set.
Via linesweep, we also store the count to be reduced once our current query's limit ends.

2 exception cases:

1. If the number is larger than the count of queries already used and the heap is empty(signifying no more queries can be used for current index), we return -1 saying we cannot convert current array to all 0.

2. If the value we pop from the heap, ends before the current index, such queries weren't used earlier, and hence, such queries can be skipped [the queries left over in the heap at the end of the traversal, are also the ones which can be counted as skipped]

# Complexity
- Time complexity: O(N+QlogQ)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(n) would be for iterating over the array. O(QlogQ) for sorting the queries.
And also, at max we might insert Q queries in the heap and pop them. Their time will also be O(QlogQ). This will be the total time, and not specific to one index. Hence, the time complexity wont be O(N*QlogQ) but O(N+QlogQ)


- Space complexity: O(N+Q)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
Space taken by queue will be O(Q) and space taken by heap will be O(Q)
Linesweep will need O(N).
Hence, total space required will be O(N+Q)

# Code
```python3 []
class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        q = deque(sorted(queries))
        c=0
        sub=[0 for _ in range(len(nums)+1)]
        countOfQueriesUsed = 0
        heap=[]
        for i in range(len(nums)):
            c-=sub[i]
            while q and q[0][0]==i:
                heapq.heappush(heap,-q.popleft()[1])
            while nums[i]>c:
                #we will have to use heap
                if not heap:
                    return -1
                last = -heapq.heappop(heap)
                if last<i:
                    continue
                else:
                    c+=1
                    sub[last+1]+=1
                    countOfQueriesUsed+=1
        #queries not used will be in heap
        return len(queries)-countOfQueriesUsed



                    
```
['Python3']