Find a range that covers all the elements of given N ranges
Given N ranges containing L and R. The task is to check or find the index(0-based) of the range which covers all the other given N-1 ranges. If there is no such range, print -1.
Note: All L and R points are distinct.
Examples:
Input: L[] = {1, 2}, R[] = {1, 2}
Output: -1Input: L[] = {2, 4, 3, 1}, R[] = {4, 6, 7, 9}
Output: 3
Range at 3rd index i.e. 1 to 9 covers
all the elements of other N-1 ranges.
Approach: Since all L and R points are distinct, find the range with the smallest L point and the range with the largest R point, if both are in the same Range, it would mean that all other ranges lie within it, otherwise it is not possible.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to check range int findRange( int n, int lf[], int rt[]) { // Index of smallest L and largest R int mnlf = 0, mxrt = 0; for ( int i = 1; i < n; i++) { if (lf[i] < lf[mnlf]) mnlf = i; if (rt[i] > rt[mxrt]) mxrt = i; } // If the same range has smallest L // and largest R if (mnlf == mxrt) return mnlf; else return -1; } // Driver Code int main() { int N = 4; int L[] = { 2, 4, 3, 1 }; int R[] = { 4, 6, 7, 9 }; cout << findRange(N, L, R); return 0; } |
Java
// Java implementation of the above approach import java.io.*; class GFG { // Function to check range static int findRange( int n, int lf[], int rt[]) { // Index of smallest L and largest R int mnlf = 0 , mxrt = 0 ; for ( int i = 1 ; i < n; i++) { if (lf[i] < lf[mnlf]) mnlf = i; if (rt[i] > rt[mxrt]) mxrt = i; } // If the same range has smallest L // and largest R if (mnlf == mxrt) return mnlf; else return - 1 ; } // Driver Code public static void main (String[] args) { int N = 4 ; int [] L = { 2 , 4 , 3 , 1 }; int []R = { 4 , 6 , 7 , 9 }; System.out.println( findRange(N, L, R)); } } // This code is contributed by anuj_67.. |
Python3
# Python3 implementation of the # above approach # Function to check range def findRange(n, lf, rt): # Index of smallest L and # largest R mnlf, mxrt = 0 , 0 for i in range ( 1 , n): if lf[i] < lf[mnlf]: mnlf = i if rt[i] > rt[mxrt]: mxrt = i # If the same range has smallest # L and largest R if mnlf = = mxrt: return mnlf else : return - 1 # Driver Code if __name__ = = "__main__" : N = 4 L = [ 2 , 4 , 3 , 1 ] R = [ 4 , 6 , 7 , 9 ] print (findRange(N, L, R)) # This code is contributed # by Rituraj Jain |
C#
// C# implementation of the // above approach using System; class GFG { // Function to check range static int findRange( int n, int []lf, int []rt) { // Index of smallest L and largest R int mnlf = 0, mxrt = 0; for ( int i = 1; i < n; i++) { if (lf[i] < lf[mnlf]) mnlf = i; if (rt[i] > rt[mxrt]) mxrt = i; } // If the same range has smallest L // and largest R if (mnlf == mxrt) return mnlf; else return -1; } // Driver Code public static void Main () { int N = 4; int [] L = { 2, 4, 3, 1 }; int []R = { 4, 6, 7, 9 }; Console.WriteLine(findRange(N, L, R)); } } // This code is contributed by anuj_67.. |
PHP
<?php // PHP implementation of the above approach // Function to check range function findRange( $n , $lf , $rt ) { // Index of smallest L and largest R $mnlf = 0; $mxrt = 0; for ( $i = 1; $i < $n ; $i ++) { if ( $lf [ $i ] < $lf [ $mnlf ]) $mnlf = $i ; if ( $rt [ $i ] > $rt [ $mxrt ]) $mxrt = $i ; } // If the same range has smallest // L and largest R if ( $mnlf == $mxrt ) return $mnlf ; else return -1; } // Driver Code $N = 4; $L = array ( 2, 4, 3, 1 ); $R = array ( 4, 6, 7, 9 ); echo findRange( $N , $L , $R ); // This code is contributed // by inder_verma ?> |
Javascript
<script> // JavaScript implementation of the above approach // Function to check range function findRange(n, lf, rt) { // Index of smallest L and largest R let mnlf = 0, mxrt = 0; for (let i = 1; i < n; i++) { if (lf[i] < lf[mnlf]) mnlf = i; if (rt[i] > rt[mxrt]) mxrt = i; } // If the same range has smallest L // and largest R if (mnlf == mxrt) return mnlf; else return -1; } // Driver Code let N = 4; let L = [ 2, 4, 3, 1 ]; let R = [ 4, 6, 7, 9 ]; document.write(findRange(N, L, R)); // This code is contributed by Surbhi Tyagi. </script> |
Output
3
Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(1) as it is using constant variables
Contact Us