O(nlgm + m) two heaps
IntuitionGo thru nums. When we encounter an "unsettled" value, we look for the query with the furthest end to cover it.Approach
Use queries to build a hashmap s
# Intuition
Go thru nums. When we encounter an "unsettled" value, we look for the query with the furthest end to cover it.
# Approach
1. Use queries to build a hashmap start2ends. It maps a single start to multiple ends.
2. Create a heap availEnds. It stores ends that have not been useds. It's a max-heap.
3. Create a heap activeEnds. It stores already-in-use ends. It's a min-heap.
4. Define a variable reduceBy whose initial value is 0. It means for val: nums encountered, how much can be reduced so far.
5. Go thru nums. For each iteration of the loop, we first add newly available ends to availEnds; and delete obsolete ends from activeEnds (and decrement reduceBy).
6. For the currently encountered val, we reduce it by reduceBy. If the remaining value is still > 0, we move available ends into active ends, and increment reduceBy.
7. If there are not enough available ends, return -1.
8. result = queries.length - totally activated ends.
9. When I finished the problem, I found that the variable reduceBy is not necessary. It can be safely replaced by activeEnds.size(). By deleting it, we can avoid maintaining that information.
# Complexity
- Time complexity:
O(nlgm + m)
- Space complexity:
O(n + m)
# Code
```java []
class Solution {
    public int maxRemoval(int[] nums, int[][] queries) {
        int len = nums.length, size = queries.length;
        HashMap<Integer, LinkedList<Integer>> start2ends = 
            new HashMap<Integer, LinkedList<Integer>>();
        for (int[] query: queries) {
            Integer start = query[0], end = query[1];
            if (!start2ends.containsKey(start)) {
                LinkedList<Integer> list = new LinkedList<Integer>();
                list.add(end);
                start2ends.put(start, list);
            } else {
                LinkedList<Integer> existing = start2ends.get(start);
                existing.add(end);
            }
        }
        PriorityQueue<Integer> availEnds = new PriorityQueue<Integer>(
            (a, b) -> b - a
        );
        PriorityQueue<Integer> activeEnds = new PriorityQueue<Integer>(
            (a, b) -> a - b
        );


        int kept = 0;
        int reduceBy = 0;
        for (int i = 0; i < len; i++) {
            // add available ends here
            if (start2ends.containsKey(i)) {
                LinkedList<Integer> existing = start2ends.get(i);
                for (Integer end: existing) {
                    availEnds.offer(end);
                }
            }

            // delete obsolete active ends here
            while (activeEnds.size() > 0) {
                Integer top = activeEnds.peek();
                if (top < i) {
                    activeEnds.poll();
                    reduceBy--;
                }
                else    break;
            }

            int val = nums[i];
            int rmg = val - reduceBy;
            if (rmg > 0) {
                if (availEnds.size() < rmg)  return -1;

                for (int j = 0; j < rmg; j++) {
                    Integer end = availEnds.peek();
                    // invalid end!!
                    if (end < i)    return -1;

                    activeEnds.offer(availEnds.poll());
                }
                reduceBy += rmg;
                kept += rmg;
            }
        }


        int result = size - kept;
        return result;
    }
}
```
['Java']