# Find the smallest range containing at least 1 element from given N ranges.

Urwashi Priya
Last Updated: May 13, 2022

## 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. codestudio

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
{
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.

1. What is the greedy approach?
Answer) As the name suggests, being greedy means finding the closest solution possible. Decisions are made from the answer domain. It finds the best solution possible at each step.

2. What is the minimisation problem?
Answer) Finding minimum possible value for the given function.

3. Which is vector and pair in C++?
Answer) Vector refers to a dynamic array, and pair refers to a container containing two data elements simultaneously.

## Key Takeaways

This article taught us how to Find the smallest range containing at least 1 element from given N ranges. We discussed its implementation using illustrations, pseudocode, and then proper code.

We hope you could take away critical techniques like analysing problems by walking over the execution of the examples and finding out the pattern followed in most problems.

Now, we recommend you practice problem sets based on binary search trees to master your fundamentals. You can get a wide range of questions similar to this on CodeStudio

It's not the end. Must solve the problem of similar types.

Happy Coding.