Given N ranges of the form [L, R], the task is to find the range having the minimum number of integers such that at least one point of all the given N ranges exists in that range.
Example:
Input: ranges[] = {{1, 6}, {2, 7}, {3, 8}, {4, 9}}
Output: 6 6
Explanation: All the given ranges contain 6 as an integer between them. Therefore, [6, 6] is a valid range having 1 integer which is the minimum possible. The other valid ranges are [4, 4] and [5, 5].Input: ranges[] = {{1, 4}, {4, 5}, {7, 9}, {9, 12}}
Output: 4 9
Approach: This problem can be solved using a Greedy Approach using the following observations:
- Suppose L is the minimum endpoint over all the given ranges. Then, it can be observed that all the given ranges must contain a point in the range [L, ∞].
- Similarly, suppose R is the maximum starting point over all the given ranges. Then, based on the similar observation as above, all the ranges must also contain a point in the range [-∞, R].
Therefore, using the above observations, the required range will be [L, R]. In cases where L > R, the answer can be any integer between L and R as all of them will make a valid range.
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 minimum range such// that alteast one point of all the// given N ranges exist in the rangevoid minRequiredRange( vector<pair<int, int> > ranges, int N){ // Stores the starting point of // the required range int L = INT_MAX; // Stores the ending point of the // required range int R = INT_MIN; // Loop to iterate over all the given // N ranges for (int i = 0; i < N; i++) { // Calculate the smallest end point // over all the given ranges L = min(L, ranges[i].second); // Calculate 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; }}// Driver Codeint main(){ vector<pair<int, int> > ranges{ { 1, 4 }, { 4, 5 }, { 7, 9 }, { 9, 12 } }; minRequiredRange(ranges, ranges.size()); return 0;} |
Java
// Java program for the above approachclass GFG { // Function to find minimum range such // that alteast one point of all the // given N ranges exist in the range public static void minRequiredRange(int[][] ranges, int N) { // Stores the starting point of // the required range int L = Integer.MAX_VALUE; // Stores the ending point of the // required range int R = Integer.MIN_VALUE; // Loop to iterate over all the given // N ranges for (int i = 0; i < N; i++) { // Calculate the smallest end point // over all the given ranges L = Math.min(L, ranges[i][1]); // Calculate the largest starting point // over all the given ranges R = Math.max(R, ranges[i][0]); } // If starting point is greater that the // end point if (R < L) { // Print any integer between L and R System.out.println(L + " " + L); } else { // Print Answer System.out.println(L + " " + R); } } // Driver Code public static void main(String args[]) { int[][] ranges = { { 1, 4 }, { 4, 5 }, { 7, 9 }, { 9, 12 } }; minRequiredRange(ranges, ranges.length); }}// This code is contributed by gfgking. |
Python3
# Python Program to implement# the above approach# Function to find minimum range such# that alteast one point of all the# given N ranges exist in the rangedef minRequiredRange(ranges, N): # Stores the starting point of # the required range L = 10 ** 9 # Stores the ending point of the # required range R = 10 ** -9 # Loop to iterate over all the given # N ranges for i in range(N): # Calculate the smallest end point # over all the given ranges L = min(L, ranges[i]["second"]) # Calculate 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 print(f"{L} {L}") else: # Print Answer print(f"{L} {R}")# Driver Coderanges = [{"first": 1, "second": 4}, {"first": 4, "second": 5}, { "first": 7, "second": 9}, {"first": 9, "second": 12}]minRequiredRange(ranges, len(ranges))# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG { // Function to find minimum range such // that alteast one point of all the // given N ranges exist in the range public static void minRequiredRange(int[, ] ranges, int N) { // Stores the starting point of // the required range int L = Int32.MaxValue; // Stores the ending point of the // required range int R = Int32.MinValue; // Loop to iterate over all the given // N ranges for (int i = 0; i < N; i++) { // Calculate the smallest end point // over all the given ranges L = Math.Min(L, ranges[i, 1]); // Calculate the largest starting point // over all the given ranges R = Math.Max(R, ranges[i, 0]); } // If starting point is greater that the // end point if (R < L) { // Print any integer between L and R Console.WriteLine(L + " " + L); } else { // Print Answer Console.WriteLine(L + " " + R); } } // Driver Code public static void Main(string[] args) { int[, ] ranges = { { 1, 4 }, { 4, 5 }, { 7, 9 }, { 9, 12 } }; minRequiredRange(ranges, ranges.GetLength(0)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find minimum range such // that alteast one point of all the // given N ranges exist in the range function minRequiredRange( ranges, N) { // Stores the starting point of // the required range let L = Number.MAX_VALUE; // Stores the ending point of the // required range let R = Number.MIN_VALUE; // Loop to iterate over all the given // N ranges for (let i = 0; i < N; i++) { // Calculate the smallest end point // over all the given ranges L = Math.min(L, ranges[i].second); // Calculate the largest starting point // over all the given ranges R = Math.max(R, ranges[i].first); } // If starting point is greater that the // end point if (R < L) { // Print any integer between L and R document.write(L + " " + L); } else { // Print Answer document.write(L + " " + R); } } // Driver Code let ranges = [ { first: 1, second: 4 }, { first: 4, second: 5 }, { first: 7, second: 9 }, { first: 9, second: 12 } ]; minRequiredRange(ranges, ranges.length); // This code is contributed by Potta Lokesh </script> |
Output
4 9
Time Complexity: O(N)
Auxiliary Space: O(1)
Share your thoughts in the comments
