1851. Minimum Interval to Include Each Query

You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1.

You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& arr, vector<int>& query) {
        int qsz = query.size(), asz = arr.size(), i = 0;
        vector<pair<int, int>> q(qsz);
        vector<int> res(qsz, -1);
        for(int i = 0; i < qsz; i++) q[i] = {query[i], i};
        sort(begin(arr), end(arr));
        sort(begin(q), end(q));
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        map<int, int> m;
        for(auto& p : q) {
            for(; i < asz && arr[i][0] <= p.first; i++) {
                pq.push({arr[i].back(), arr[i].back() - arr[i].front() + 1});
                m[arr[i].back() - arr[i].front() + 1]++;
            }
            while(!pq.empty() && pq.top().first < p.first) {
                if(m[pq.top().second] == 1) m.erase(pq.top().second);
                else --m[pq.top().second];
                pq.pop();
            }
            if(!m.empty()) res[p.second] = m.begin()->first;
        }

        return res;
    }
};