1851. Minimum Interval to Include Each Query (Hard)

Description Link to heading

1851. Minimum Interval to Include Each Query (Hard)

Solution Link to heading

First, it should be noted that sorting the intervals array will not affect the result. Secondly, sorting the queries array will not have a significant impact on the answer. It merely changes the order of the answers. We just need to associate the result of each query with its corresponding index in the original queries array.

For convenience, let’s convert the queries array into a vector<pair<int, int>> qrs; where the first element represents the value to be queried, and the second element represents its index in the queries array. Then, we sort the qrs vector in ascending order based on the first element.

Next, we prepare to iterate through the qrs vector. Since the intervals array is already sorted in ascending order based on the left endpoint, we compare the current query with intervals[idx][0]. If intervals[idx][0] <= query, we enqueue the intervals (fulfilling half of the required conditions), and increment idx to indicate that we have considered this interval. We continue this process until idx >= queries.size() or intervals[idx][0] > query.

Next, we compare the current query with the right endpoint of the top interval in the heap (where the top interval has the smallest length). If the right endpoint is smaller than query, we pop the interval out of the heap until the heap is empty or the right endpoint of the top interval is >= query.

Finally, we can update the minimum interval length corresponding to the query.

Code Link to heading

class Solution {
  public:
    vector<int> minInterval(vector<vector<int>> &intervals, vector<int> &queries) {
        sort(intervals.begin(), intervals.end());
        using pii = pair<int, int>;
        vector<pii> qrs;
        int m = intervals.size(), n = queries.size();
        for (int i = 0; i < n; ++i) {
            qrs.emplace_back(queries[i], i);
        }
        std::sort(qrs.begin(), qrs.end());
        vector<int> ans(n, -1);
        priority_queue<pii, vector<pii>, greater<pii>> pq; // pair.first => right - left + 1，pair.second => right
        int idx = 0;
        for (int i = 0; i < n; ++i) {
            while (idx < m && intervals[idx][0] <= qrs[i].first) {
                pq.push({intervals[idx][1] - intervals[idx][0] + 1, intervals[idx][1]});
                ++idx;
            }
            while (!pq.empty() && pq.top().second < qrs[i].first) {
                pq.pop();
            }
            if (!pq.empty()) {
                ans[qrs[i].second] = pq.top().first;
            }
        }
        return ans;
    }
};