# Find the minimum range size that contains the given element for Q queries

Given an array **Intervals[]** consisting of **N** pairs of integers where each pair is denoting the value range **[L, R]**. Also, given an integer array** Q[] **consisting of **M** queries. For each query, the task is to find the size of the smallest range that contains that element. Return** -1** if no valid interval exists.

**Examples**

Input:Intervals[] = [[1, 4], [2, 3], [3, 6], [9, 25], [7, 15], [4, 4]]

Q[] = [7, 50, 2]Output:[9, -1, 2]Explanation:Element 7 is in the range [7, 15] only therefore, the answer will be 15 – 7 + 1 = 8. Element 50 is in no range. Therefore, the answer will be -1.

Similarly, element 2 is in the range [2, 3] and [1, 4] but the smallest range is [2, 3] therefore, the answer will be 3-2+1 = 2.

Input:Intervals[] = [[1, 4], [2, 4], [3, 6]]

Q[] = [2, 3]Output:[3, 3]

**Naive Approach: **The simplest approach to solve the problem is to Iterate through the array** range[] **and for each query find the smallest range that contains the given elements.

**Time Complexity: **O(N×M)**Auxiliary Space: **O(M)

**Efficient Approach: **The approach mentioned above can be optimized further by using priority_queue. Follow the steps below to solve the problem:

- Initialize a vector of vectors, say
**Queries**and insert all the queries in the array**Q**along with its index. - Sort the vector
**Intervals**and**Queries**using the default sorting function of the vector. - Initialize a priority_queue, say
**pq**with key as the size of Interval and value as right bound of the range. - Initialize a vector, say
**result**that will store the size of minimum range for each query. - Initialize an integer variable, say
**i**that will keep the track of traversed elements of the array**Intervals**. - Iterate in the range
**[0, M-1]**using the variable**j**and perform the following steps:- Iterate while
**i < Intervals.size()**and**Intervals[i][0] <= Queries[j][0]**, insert**-(Intervals[i][1] – Intervals[i][0] + 1), Intervals[i][1]**as pair and increment the value of**i**by**1**. - Now remove all the elements from the priority_queue
**pq**with the right element less than**Qeries[j][0]**. - If the size of priority_queue
**pq>0**, then modify the value of**result[Queries[j][1]]**as**pq.top()[0]**.

- Iterate while
- Return the array
**res[]**as the answer.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` ` ` `// Function to find the size of minimum` `// Interval that contains the given element` `vector<` `int` `> minInterval(vector<vector<` `int` `> >& intervals,` ` ` `vector<` `int` `>& q)` `{` ` ` `// Store all the queries` ` ` `// along with their index` ` ` `vector<vector<` `int` `> > queries;` ` ` ` ` `for` `(` `int` `i = 0; i < q.size(); i++)` ` ` `queries.push_back({ q[i], i });` ` ` ` ` `// Sort the vector intervals and queries` ` ` `sort(intervals.begin(), intervals.end());` ` ` `sort(queries.begin(), queries.end());` ` ` ` ` `// Max priority queue to keep track` ` ` `// of intervals size and right value` ` ` `priority_queue<vector<` `int` `> > pq;` ` ` ` ` `// Stores the result of all the queries` ` ` `vector<` `int` `> result(queries.size(), -1);` ` ` ` ` `// Current position of intervals` ` ` `int` `i = 0;` ` ` ` ` `for` `(` `int` `j = 0; j < queries.size(); j++) {` ` ` ` ` `// Stores the current query` ` ` `int` `temp = queries[j][0];` ` ` ` ` `// Insert all the intervals whose left value` ` ` `// is less than or equal to the current query` ` ` `while` `(i < intervals.size()` ` ` `&& intervals[i][0] <= temp) {` ` ` ` ` `// Insert the negative of range size and` ` ` `// the right bound of the interval` ` ` `pq.push(` ` ` `{ -intervals[i][1] + intervals[i][0] - 1,` ` ` `intervals[i++][1] });` ` ` `}` ` ` ` ` `// Pop all the intervals with right value` ` ` `// less than the current query` ` ` `while` `(!pq.empty() && temp > pq.top()[1]) {` ` ` `pq.pop();` ` ` `}` ` ` ` ` `// Check if the valid interval exists` ` ` `// Update the answer for current query` ` ` `// in result array` ` ` `if` `(!pq.empty())` ` ` `result[queries[j][1]] = -pq.top()[0];` ` ` `}` ` ` `// Return the result array` ` ` `return` `result;` `}` ` ` `// Driver Code` `int` `main()` `{` ` ` `// Given Input` ` ` `vector<vector<` `int` `> > intervals` ` ` `= { { 1, 4 }, { 2, 3 }, { 3, 6 }, { 9, 25 }, { 7, 15 }, { 4, 4 } };` ` ` `vector<` `int` `> Q = { 7, 50, 2, 3, 4, 9 };` ` ` ` ` `// Function Call` ` ` `vector<` `int` `> result = minInterval(intervals, Q);` ` ` ` ` `// Print the result for each query` ` ` `for` `(` `int` `i = 0; i < result.size(); i++)` ` ` `cout << result[i] << ` `" "` `;` ` ` `return` `0;` `}` |

**Output**

9 -1 2 2 1 9

**Time Complexity:** O(NlogN+MlogM)**Auxiliary Space**: O(N+M)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.