## Introduction

In this blog, we will discuss an array minimisation problem that has been asked frequently in Interviews.

The problem is to** Find the smallest range containing at least 1 element from given N ranges.**

We are given N ranges, and our task is to search for the smallest range that contains at least 1 element from all the given ranges.

We need to find the minimum and a maximum number such that maximum-minimum is minimum and at least one number from each range should be in {minimum number, maximum number}. We need to choose the minimum number and maximum number as close as possible. Our minimum number should be as large as possible, and the maximum number should be as small as possible.

**Example:** Say, the ranges given are: {{1,6}, {2,7}, {3,8}, {4,9}}

Here all ranges contains 4.

So, our answer can be [4,4].

In this way, we need to find the most minimised answer.

## Approach

The** approach** to Find the smallest range containing at least 1 element from given N ranges can be best solved by the greedy approach.

Best Time Complexity = n. Since the array will be traversed only once.

Declare two variables to store the starting and ending point of the range.

⬇

Calculate the smallest endpoint and largest starting point by looping over all the given ranges.

⬇

If the starting point is greater than the endpoint, print any integer between starting and ending points.

⬇

Else print the starting and ending points.

Time Complexity = n

∵Time Complexity for traversing = n

Till now, I assume you have got the basic and conceptual idea of what has been asked in the problem statement. So, I strongly recommend you first try and solve some related problems. __Coding Ninjas Studio__

Please have a look at the algorithm, and then again, you must give it a try.

### PseudoCode

**Algorithm**

___________________________________________________________________

**procedure** minRequiredRange(vector<pair<int, int> > ranges, int N):

___________________________________________________________________

**1.** L = INT_MAX, R = INT_MIN

**2. ****Begin loop from 0 to N:**

**3.** L = min(L, ranges[i].second).

**4.** ** **R = max(R, ranges[i].first)

**5. End loop**

**6. **if (R < L): return L and L

**7. **Else: return L and R.

**end procedure**

___________________________________________________________________

### Implementation in C++

```
// Find smallest range containing at least a single element from given N ranges
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum range or domain
void minRequiredRange(vector<pair<int, int>> ranges, int N)
{
// variable to store the starting of the range
int L = INT_MAX;
// variable to store the ending of the range
int R = INT_MIN;
// Loop to iterate over all N ranges given in problem statement
for (int i = 0; i < N; i++)
{
// Calculate the smallest end point over all the given ranges
L = min(L, ranges[i].second);
// Calcuate the largest starting point over all the given ranges
R = max(R, ranges[i].first);
}
// If starting point is greater that the end point
if (R < L)
{
// Print any integer between L and R
cout << L << " " << L;
}
else
{
// Print Answer
cout << L << " " << R;
}
}
int main()
{
vector<pair<int, int>> ranges
{
{ 1, 4 },
{ 4, 5 },
{ 7, 9 },
{ 9, 12 }
};
minRequiredRange(ranges, ranges.size());
return 0;
}
```

**Output:**

`4 9`

#### Complexity Analysis

**Time Complexity:** **O(n).**

**Analysing Time Complexity:**

Since the array is traversed only once.

**Space complexity**: O(1) since no extra variable is used.