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

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;
}

You can also try this code with Online C++ Compiler

Run Code

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.