Description

Submission

class Solution {
    typedef pair<int, int> PII;
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        vector<PII> queriesPair;
        for(int i = 0; i < queries.size(); ++i) {
            queriesPair.push_back({queries[i], i});
        }
        sort(queriesPair.begin(), queriesPair.end());
        sort(intervals.begin(), intervals.end());

        priority_queue<PII, vector<PII>, greater<>> pq;

        int ptr = 0;
        vector<int> rets(queries.size(), -1);

        for(auto& p: queriesPair) {
            auto [query, idx] = p;

            for(; ptr < intervals.size() && intervals[ptr][0] <= query; ++ptr) {
                pq.emplace(intervals[ptr][1] - intervals[ptr][0] + 1, intervals[ptr][1]);
            }
            
            while(!pq.empty()) {
                auto [duration, right] = pq.top();

                if(right >= query) {
                    rets[idx] = duration;
                    break;
                }

                pq.pop();
            }
        }
        return rets;
    }
};


// sort all the queries based on time(increasing)
// sort all the intervals based on left boundary(increasing)
// push all the intervals with satisfied left boundary into pq(increasing interval)
// find the satisfied right boundary from the pq
// offline: should recover the index order