解法：贪心 & 差分 & 单调指针 & 优先队列

题目的包装和 零数组变换 I 一样，问的其实是这样一个问题：

在 queries 中给定若干个区间，从中删除尽量多的区间，使得 nums 中的每个元素都能至少被 nums[i] 个剩余区间覆盖。

删除尽量多的区间，其实就是保留尽量少的区间。我们可以利用贪心的思想解决问题。一开始先不保留任何区间，从左到右枚举 nums 中的每个元素，。如果当前元素的覆盖数不够，我们再不断加入能覆盖该元素的区间，直到覆盖数满足要求。

如果同时有很多区间都能覆盖当前元素，应该加入哪个呢？反正当前元素左边都已经符合条件了，我们只要为后面的元素考虑即可。因此我们应该加入右端点尽量大的区间，这样才能尽可能增加后续元素的覆盖数。

怎么知道哪些区间可以覆盖当前元素，并取出右端点最大的区间？可以用一个单调指针和优先队列来维护。怎么维护当前元素的覆盖数？可以用差分数组来维护。详见参考代码。

复杂度 $\mathcal{O}(n + q\log q)$。

参考代码（c++）

###cpp

class Solution {
public:
    int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size(), q = queries.size();
        // 所有区间按左端点从小到大排序，方便之后用单调指针维护
        sort(queries.begin(), queries.end());
        // now：当前元素的覆盖数
        // ans：最少要选几个区间
        int now = 0, ans = 0;
        // pq：优先队列（大根堆），记录了所有左端点小等于当前下标的，且还未选择的区间的右端点
        // 这样，如果堆顶元素大等于当前下标，那么它就是能覆盖当前元素且右端点尽量大的区间
        priority_queue<int> pq;
        // f：差分数组，f[i] 表示有几个区间在下标 i 结束
        int f[n + 1];
        memset(f, 0, sizeof(f));
        // i：从左到右枚举每个元素，检查覆盖数
        // j：单调指针，指向左端点大于当前下标的下一个区间
        for (int i = 0, j = 0; i < n; i++) {
            // 减去差分数组中记录的区间结束数量
            now -= f[i];
            // 移动单调指针，把左端点小等于当前下标的区间加入优先队列
            while (j < q && queries[j][0] <= i) pq.push(queries[j][1]), j++;
            // 如果覆盖数不够，则尝试从优先队列中取出区间
            while (now < nums[i] && !pq.empty()) {
                int t = pq.top(); pq.pop();
                if (t >= i) {
                    // 堆顶区间能覆盖当前元素，那么加入该区间
                    now++;
                    ans++;
                    // 别忘了在差分数组里记录该区间的结束位置
                    f[t + 1]++;
                }
            }
            // 优先队列掏空了，覆盖数还是不够，无解
            if (now < nums[i]) return -1;
        }
        // 删除尽量多的区间，其实就是保留尽量少的区间
        return q - ans;
    }
};