Java O(N + KLogK) solution with Pseudo Code for explanation
IntuitionIntution is to always use the query that impacts the largest range of indexes ahead of the current index.ApproachSort the queries array so that we can
# Intuition\nIntution is to always use the query that impacts the largest range of indexes ahead of the current index.\n\n# Approach\nSort the queries array so that we can pick up elements that actually impact current index while traversing nums array. Following is the pseudo code for  the approach -\n\n    sort queries array in asceneding order of left of the range.\n    maxHeap = create a heap based on the right in descending order.\n    range i 0 to nums.length:\n        while idx < queries.length && i >= queries[idx][0]\n            maxHeap.offer(queries[idx]);\n        while maxHeap is not empty && nums[i] > presum + line[i]\n            range = poll(maxHeap)\n            if the range[1] < i \n                then we return -1; // the reason for this is because we have used all the ranges that could impact i and nums[i] cannot be reduced to 0.\n            update line based on the range.        \n        //This checks for edge case where we used all the queries and the last element could not be reduced to zero.\n        if maxHeap is empty and presum + line[i] < nums[i]\n            return -1;\n        presum += line[i];\n    return size of maxHeap;\n\n# Complexity\n- Time complexity:\nO(N + KLogK), where N = nums.length and K = queries.length\n\n- Space complexity:\nO(N + K), where N = nums.length and K = queries.length\n\n# Code\n```java []\nclass Solution {\n    public int maxRemoval(int[] nums, int[][] queries) {\n        int[] line = new int[nums.length + 1];\n        Arrays.sort(queries, (x, y) -> x[0] - y[0]);\n        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((x, y) -> y[1] - x[1]);\n        int presum = 0;\n        int ans = 0;\n        int idx = 0;\n\n        for (int i = 0; i < nums.length; i++) {\n            while(idx < queries.length && i >= queries[idx][0]) {\n                maxHeap.offer(queries[idx++]);\n            }\n\n            while(!maxHeap.isEmpty() && nums[i] > presum + line[i]) {\n                int[] range = maxHeap.poll();\n\n                // have used all ranges that could increment i\n                if (range[1] < i)\n                    return -1;\n\n                line[i]++;\n                line[range[1] + 1]--;\n            }\n\n            // edge case\n            if (maxHeap.isEmpty() && nums[i] > presum + line[i]) {\n                return -1;\n            }\n\n            presum += line[i];\n        }\n\n        return maxHeap.size();\n    }\n}\n```
['Java']