Encuentre un rango que cubra todos los elementos de N rangos dados

N rangos dados que contienen L y R. La tarea es verificar o encontrar el índice (basado en 0) del rango que cubre todos los demás rangos N-1 dados. Si no existe tal rango, imprima -1.
Nota: Todos los puntos L y R son distintos.
Ejemplos: 
 

Entrada: L[] = {1, 2}, R[] = {1, 2} 
Salida: -1
Entrada: L[] = {2, 4, 3, 1}, R[] = {4, 6, 7, 9} 
Salida: 3 
Rango en el 3er índice, es decir, 1 a 9 cubre 
todos los elementos de otros N-1 rangos.

Enfoque: dado que todos los puntos L y R son distintos, encuentre el rango con el punto L más pequeño y el rango con el punto R más grande , si ambos están en el mismo rango, significaría que todos los demás rangos se encuentran dentro de él, de lo contrario es imposible.
A continuación se muestra la implementación del enfoque anterior: 
 

// 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 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 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# 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 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
?>

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

3

Complejidad de tiempo: O(N)