Editorial: LeetCode 1851 Minimum Interval to Include Each Query
https://leetcode.com/problems/minimum-interval-to-include-each-query/ from Google
Thinking process:
This question has the same concept in https://www.krammerliu.com/blog/leetcode-1847-closest-room/. The queries are given at once so we can do offline search instead of online search, which means we can change the order of the queries.
Since we want to find the minimum interval to cover the query, instead of starting from queries, we can start from the interval. We start from the smallest interval and see what queries it covers. This interval is the answer for those queries. Then, we remove those queries, and do the same thing for the second smallest interval.
The process is like below when intervals = [[1,4],[2,4],[3,6],[4,4]] and queries = [2,3,4,5]
Here is the code.
1class Solution {
2public:
3 vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
4 int Q = queries.size();
5 set<vector<int>> s;
6 for (int i=0; i<Q; i++) {
7 s.insert({queries[i], i});
8 }
9 sort(intervals.begin(), intervals.end(), [](const auto& i1, const auto& i2){
10 return i1[1] - i1[0] < i2[1] - i2[0];
11 });
12 vector<int> ans(Q, -1);
13 for (auto i : intervals) {
14 int l = i[0], r = i[1];
15 int size = r - l + 1;
16 auto it1 = s.lower_bound({l, 0});
17 auto it2 = s.upper_bound({r, Q});
18 for (auto it=it1; it!=it2; it++) {
19 vector<int> v = *it;
20 ans[v[1]] = size;
21 }
22 auto it = it1;
23 while (it != it2) {
24 auto nxt = next(it);
25 s.erase(it);
26 it = nxt;
27 }
28 }
29 return ans;
30 }
31};