codekofi
← All questions

Minimum Interval to Include Each Query

HardIntervals

The problem

For each query value, find the shortest interval that contains it, and report that interval's length — its end minus its start, plus one.

Report -1 for a query no interval contains. Answers must be returned in the order the queries were given.

minInterval({{1,4},{2,4},{3,6},{4,4}}, {2,3,4,5})

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1vector<int> minInterval(vector<vector<int>> intervals,
2 const vector<int>& queries) {
3
4 int n = queries.size();
5 vector<pair<int, int>> asked(n);
6
7 for (int i = 0; i < n; i++) {
8 asked[i] = {queries[i], i};
9 }
10
11 sort(asked.begin(), asked.end());
12 sort(intervals.begin(), intervals.end());
13
14 using Item = pair<int, int>;
15 priority_queue<Item, vector<Item>, greater<Item>> live;
16
17 vector<int> ans(n, -1);
18 int at = 0;
19
20 for (const auto& [q, id] : asked) {
21
22 while (at < (int)intervals.size() && intervals[at][0] <= q) {
23
24 int width = intervals[at][1] - intervals[at][0] + 1;
25
26 live.push({width, intervals[at][1]});
27 at++;
28 }
29
30 while (!live.empty() && live.top().second < q) {
31 live.pop();
32 }
33
34 if (!live.empty()) {
35 ans[id] = live.top().first;
36 }
37 }
38
39 return ans;
40}
1vector<int> minInterval(vector<vector<int>> intervals,
2 const vector<int>& queries) {
3
4 int n = queries.size();
5 vector<pair<int, int>> asked(n);
6
7 for (int i = 1; i < n; i++) {
8 asked[i] = {queries[i], i};
9 }
10
11 sort(asked.begin(), asked.end());
12 sort(intervals.begin(), intervals.end());
13
14 using Item = pair<int, int>;
15 priority_queue<Item, vector<Item>, greater<Item>> live;
16
17 vector<int> ans(n, -1);
18 int at = 1;
19
20 for (const auto& [q, id] : asked) {
21
22 while (at < (int)intervals.size() && intervals[at][0] <= q) {
23
24 int width = intervals[at][1] - intervals[at][0] + 1;
25
26 live.push({width, intervals[at][1]});
27 at++;
28 }
29
30 while (!live.empty() && live.top().second < q) {
31 live.pop();
32 }
33
34 if (!live.empty()) {
35 ans[id] = live.top().first;
36 }
37 }
38
39 return ans;
40}
1vector<int> minInterval(vector<vector<int>> intervals,
2 const vector<int>& queries) {
3
4 int n = queries.size();
5 vector<pair<int, int>> asked(n);
6
7 for (int i = 1; i < n; i++) {
8 asked[i] = {queries[i], i};
9 }
10
11 sort(asked.begin(), asked.end());
12 sort(intervals.begin(), intervals.end());
13
14 using Item = pair<int, int>;
15 priority_queue<Item, vector<Item>, greater<Item>> live;
16
17 vector<int> ans(n, -1);
18 int at = 0;
19
20 for (const auto& [q, id] : asked) {
21
22 while (at < (int)intervals.size() && intervals[at][0] <= q) {
23
24 int width = intervals[at][1] - intervals[at][0] + 1;
25
26 at++;
27 }
28
29 while (!live.empty() && live.top().second < q) {
30 live.pop();
31 }
32
33 if (!live.empty()) {
34 ans[id] = live.top().first;
35 }
36 }
37
38 return ans;
39}