Compruebe si algún intervalo se superpone completamente al otro

Un intervalo se representa como una combinación de la hora de inicio y la hora de finalización. Dado un conjunto de intervalos, necesitamos escribir un programa para verificar si algún intervalo se superpone  completamente al otro.

Ejemplos: 

Input:  arr[] = {{1, 3}, {1, 7}, {4, 8}, {2, 5}}
Output: true
The intervals {1, 3} completely overlaps in {1, 7}. 

Input:  arr[] = {{1, 3}, {7, 9}, {4, 6}, {10, 13}}
Output: false
No pair of intervals overlap. 

Una solución simple es considerar cada par de intervalos y verificar si el par se superpone o no. La complejidad temporal de esta solución es O(n ² ). 

Una mejor solución es usar Sorting . A continuación se muestra el algoritmo completo. 
1) Ordene todos los intervalos en orden creciente de tiempo de inicio. Este paso toma tiempo O(n Logn) . 
2) En la array ordenada, si el tiempo de finalización de un intervalo no es mayor que el final del intervalo anterior, entonces hay una superposición completa. Este paso toma tiempo O(n) . 

A continuación se muestra una implementación del enfoque anterior:  

// A C++ program to check if any two intervals
// completely overlap
#include <bits/stdc++.h>
using namespace std;
 
// An interval has start time and end time
struct Interval {
    int start;
    int end;
};
 
// Compares two intervals according to their starting
// time. This is needed for sorting the intervals
// using library function std::sort().
bool compareInterval(Interval i1, Interval i2)
{
    return (i1.start < i2.start) ? true : false;
}
 
// Function to check if any two intervals
// completely overlap
bool isOverlap(Interval arr[], int n)
{
    // Sort intervals in increasing order of
    // start time
    sort(arr, arr + n - 1, compareInterval);
 
    // In the sorted array, if end time of an
    // interval is not more than that of
    // end of previous interval, then there
    // is an overlap
    for (int i = 1; i < n; i++)
        if (arr[i].end <= arr[i - 1].end)
            return true;
 
    // If we reach here, then no overlap
    return false;
}
 
// Driver code
int main()
{
    // 1st example
    Interval arr1[] = { { 1, 3 }, { 1, 7 }, { 4, 8 },
                                          { 2, 5 } };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    if (isOverlap(arr1, n1))
        cout << "Yes\n";
    else
        cout << "No\n";
 
    // 2nd example
    Interval arr2[] = { { 1, 3 }, { 7, 9 }, { 4, 6 },
                                         { 10, 13 } };
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    if (isOverlap(arr2, n2))
        cout << "Yes\n";
    else
        cout << "No\n";
 
    return 0;
}

<script>
    // A JavaScript program to check if any two intervals
    // completely overlap
 
    // An interval has start time and end time
 
    // Compares two intervals according to their starting
    // time. This is needed for sorting the intervals
    // using library function std::sort().
    const compareInterval = (i1, i2) => i1.start - i2.start;
 
    // Function to check if any two intervals
    // completely overlap
    const isOverlap = (arr, n) => {
     
        // Sort intervals in increasing order of
        // start time
        arr.sort(compareInterval);
 
        // In the sorted array, if end time of an
        // interval is not more than that of
        // end of previous interval, then there
        // is an overlap
        for (let i = 1; i < n; i++)
            if (arr[i].end <= arr[i - 1].end)
                return true;
 
        // If we reach here, then no overlap
        return false;
    }
 
    // Driver code
 
    // 1st example
    let arr1 = [
        { start: 1, end: 3 },
        { start: 1, end: 7 },
        { start: 4, end: 8 },
        { start: 2, end: 5 }
    ];
    let n1 = arr1.length;
    if (isOverlap(arr1, n1))
        document.write("Yes<br/>");
    else
        document.write("No<br/>");
 
    // 2nd example
    let arr2 = [
        { start: 1, end: 3 },
        { start: 7, end: 9 },
        { start: 4, end: 6 },
        { start: 10, end: 13 }
    ];
    let n2 = arr2.length;
    if (isOverlap(arr2, n2))
        document.write("Yes<br/>");
    else
        document.write("No<br/>");
 
    // This code is contributed by rakeshsahni
 
</script>

Producción: 

Yes
No

Complejidad temporal: O(n log n).

Espacio Auxiliar: O(1)