Double Heap Solution Explained Clearly
IntuitionThe problem involves optimally choosing queries for each nums[i]. To make a selection, we need to know the context-what are our available intervals for
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem involves optimally choosing queries for each nums[i]. To make a selection, we need to know the context-what are our available intervals for some index i, and how many existing intervals already cover it. In addition, suppose we have k existing intervals that cover point i but we need n more, how should we select remaining n intervals. You should make the observation  that we definitely want to priortize intervals with the farthest end point because we can hold on to them as an existing interval the longest (thus less intervals to add in the long run).

# Approach
<!-- Describe your approach to solving the problem. -->
We will use a candidates and chosen heap. The candidates heap will hold the context-the pool of intervals that are valid for each iteration. We will take from candidates to chosen to attempt to reduce a particular value in nums. It makes sense that that candidates should be a max heap since the best available interval is one with the largest (farthest) end point within that context. To do this in python, we add negative values to the min heap to have a max heap. As we traverse nums left to right, we add the next batch of available intervals that fit within this context to candidates. But there's another thing we have to worry about: what happens of the end time for a particular interval is up, how do we remove it? The good news is we don't have to worry about that. We handle it by carefully adding to our chosen heap which will be described later.

chosen is where we will store queries that we selected from candidates. We pop from candidates to insert into chosen. Similar to the candidates heap, we will need to eliminate intervals that go out of range for chosen. Except, we will explcitily be removing them with each iterations. So how do we find out which interval to remove? If we add the end point to chosen, and make it a min heap, then the top of the heap will always give us the interval with the earliest finish time. Therefore, we continue popping from chosen until the remaining elements are valid selections. Now we guranteed that chosen will only have valid query selection, so there's a case where thats enough, or we need to draw from the candidate pool. 

Suppose we need more queries from candidates. Remember that we never removed intervals that are out of range, but that's okay because candidates is a max heap sorted by farthest end point. We will just acknowledge that if we continue popping from the candidates, the farthest end point will be less than our current position i. In which case, that is all valid intervals we could take from candidates. 

Note that since we need to maximize the number of queries removed, that means each query we select has to be essential. So that means the size of chosen must never exceed nums[i], and thus if we are ever short, we stop as soon as we have as many querires as nums[i]. But there could always be the case that we have no candidates to choose from, or whatever candidates remain are out of bounds, so that marks an invalid solution. Our acutal solution will be the length of queries - added, where added is increment each time we take from candidate to add to chosen.

We will traverse nums from left to right, so it makes sense to sort the queries by soonest starting time so that we know the next set of available intervals with each iteration of the for loop.  


# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(nlogn)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(n)

# Code
```python3 []
class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        queries.sort() #Sort by soonest start time
        candidates = []
        chosen = []
        j = 0
        ans = 0
        for i in range(len(nums)):
            while j < len(queries) and queries[j][0] <= i: # with each iteration, we will encounter new valid intervals, add them
                heapq.heappush(candidates,-queries[j][1])
                j+= 1
            while chosen and chosen[0] < i: # remove out of range selected intervals
                heapq.heappop(chosen)
            size = len(chosen)
            need = nums[i] - size  # calculate if any remaining intervals are needed, and pull from candidate as much as possible until either empty, or the next interval finishes before position i
            while need > 0 and candidates and -candidates[0] >= i:
                heapq.heappush(chosen,-heapq.heappop(candidates))
                need -= 1
                ans+= 1 # this is an interval that was necessary to add
            if need > 0:  # if we can't find enough intervals, invalid
                return -1
        return len(queries)-ans  # we can subtract off the essential intervals the max number of intervals that are redundant

            




        
```
['Python3']