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

Frequently Asked Questions

  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.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think