题目描述

给你一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [l_i, r_i]。

每一个 queries[i] 表示对于 nums 的以下操作：

• 将 nums 中下标在范围 [l_i, r_i] 之间的每一个元素 最多 减少 1。
• 坐标范围内每一个元素减少的值相互 独立。

零数组 指的是一个数组里所有元素都等于 0。

请你返回 最多 可以从 queries 中删除多少个元素，使得 queries 中剩下的元素仍然能将 nums 变为一个 零数组。如果无法将 nums 变为一个 零数组，返回 -1。

样例

输入：nums = [2,0,2], queries = [[0,2],[0,2],[1,1]]

输出：1

解释：

删除 queries[2] 后，nums 仍然可以变为零数组。

对于 queries[0]，将 nums[0] 和 nums[2] 减少 1，将 nums[1] 减少 0。
对于 queries[1]，将 nums[0] 和 nums[2] 减少 1，将 nums[1] 减少 0。

输入：nums = [1,1,1,1], queries = [[1,3],[0,2],[1,3],[1,2]]

输出：2

解释：

可以删除 queries[2] 和 queries[3]。

输入：nums = [1,2,3,4], queries = [[0,3]]

输出：-1

解释：

nums 无法通过 queries 变成零数组。

限制

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= l_i <= r_i < nums.length

算法

(贪心，堆) $O(n + m \log m)$

1. 定义一个可取区间的候选集合。
2. 遍历数组，如果当前位置 $i$ 被区间覆盖的次数小于 $nums(i)$，则从可取区间中选择一个结束位置最大的区间，覆盖到当前位置上。不断重复这个过程，直到候选集合为空，或者满足了条件。
3. 从小到大排序所有区间，并使用堆维护候选集合。如果当前位置 $i$ 大于等于当前的区间，则将这个区间插入到候选集合中。采用懒删除的方式，如果取出区间的终点小于 $i$，则直接返回 $-1$，即这个位置不会被满足。
4. 可以使用差分思想维护某个位置被区间覆盖的次数。

时间复杂度

• 排序区间的时间复杂度为 $O(m \log m)$。
• 每个区间最多进堆一次，出堆一次，故这部分的总时间复杂度为 $O(m \log m)$。
• 遍历数组每个位置一次，但每个位置可能会循环很多次，但循环最多累加下来不超过 $O(n + m)$ 次。
• 故总时间复杂度为 $O(n + m \log m)$。

空间复杂度

• 需要 $O(n + m)$ 的额外空间存储差分数组，排序的系统栈和堆。

C++ 代码

#define PII pair<int, int>

class Solution {
public:
    int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
        const int n = nums.size(), m = queries.size();

        priority_queue<PII> heap;
        sort(queries.begin(), queries.end());

        vector<int> p(n + 1, 0);

        int v = 0, ans = m;
        for (int i = 0, j = 0; i < n; i++) {
            v += p[i];

            while (j < m && queries[j][0] <= i) {
                heap.push(make_pair(queries[j][1], j));
                ++j;
            }

            while (v < nums[i]) {
                if (heap.empty())
                    return -1;

                auto t = heap.top();
                heap.pop();

                if (queries[t.second][1] < i)
                    return -1;

                ++v;
                --p[queries[t.second][1] + 1];
                --ans;
            }
        }

        return ans;
    }
};