Encuentre el índice del intervalo no superpuesto más cercano a la derecha de cada uno de los N intervalos dados

Dada una array arr[] de N intervalos, la tarea es calcular el índice del intervalo más cercano a la derecha de cada uno de los N intervalos dados que no se superponen con el intervalo actual.  

Ejemplos: 

Entrada: arr[] = {{3, 4}, {2, 3}, {1, 2}}
Salida: -1 0 1
Explicación: para el intervalo arr[0], no existe ningún intervalo a la derecha del mismo . Para el intervalo arr[1], es decir, [2, 3], el intervalo [3, 4] es el intervalo más cercano a su derecha que no se superpone. Por lo tanto, la respuesta requerida para arr[1] es 0. Para el intervalo arr[2], tanto arr[1] como arr[2] están en su lado derecho y no se superponen con arr[2], sino con arr[1] es el más cercano entre ellos.

Entrada: arr[] = {{1, 4}, {3, 4}, {2, 3}}
Salida: -1 -1 1
 

Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso con la ayuda de una búsqueda binaria . La idea es ordenar los intervalos en orden creciente de sus puntos de partida y encontrar el intervalo más cercano a la derecha para cada intervalo. A continuación se detallan los pasos a seguir:

• Cree un vector de pares V que almacene los puntos de partida y el índice de cada intervalo en arr[] .
• Ordena el vector V en orden creciente de los puntos iniciales.
• Repita la array arr[] y, para cada índice, encuentre el índice del intervalo más cercano a la derecha de modo que no se superponga con el intervalo actual mediante la función de límite inferior .

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

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the index of closest
// non overlapping interval to the right
// of each of the given N intervals
vector<int> closestInterval(
    vector<pair<int, int> > arr,
    int N)
{
    // Vector to store starting value,
    // index pair of arr[]
    vector<pair<int, int> > V;
 
    // Loop to iterate arr[]
    for (int i = 0; i < N; i++) {
        V.push_back({ arr[i].first, i });
    }
 
    // Sort the vector V
    sort(V.begin(), V.end());
 
    // Stores the resultant vector
    vector<int> res(N, -1);
 
    // Loop to iterate arr[]
    for (int i = 0; i < N; i++) {
        // Calculate the closest
        // interval to the right
        auto it = lower_bound(
            V.begin(), V.end(),
            make_pair(arr[i].second, 0));
 
        // If a valid interval
        // exist update res
        if (it != V.end()) {
            int idx = it - V.begin();
 
            // Update res
            res[i] = V[idx].second;
        }
    }
 
    // Return Answer
    return res;
}
 
// Driver Code
int main()
{
    vector<pair<int, int> > arr{ { 1, 4 },
                                 { 3, 4 },
                                 { 2, 3 } };
 
    for (auto x : closestInterval(arr, arr.size())) {
        cout << x << " ";
    }
 
    return 0;
}

# python3 program of the above approach
import bisect
 
# Function to find the index of closest
# non overlapping interval to the right
# of each of the given N intervals
def closestInterval(arr, N):
 
    # Vector to store starting value,
    # index pair of arr[]
    V = []
 
    # Loop to iterate arr[]
    for i in range(0, N):
        V.append([arr[i][0], i])
 
    # Sort the vector V
    V.sort()
 
    # Stores the resultant vector
    res = [-1 for _ in range(N)]
 
    # Loop to iterate arr[]
    for i in range(0, N):
        # Calculate the closest
        # interval to the right
        it = bisect.bisect_left(V, [arr[i][1], 0])
 
        # If a valid interval
        # exist update res
        if (it != len(V)):
            idx = it
 
            # Update res
            res[i] = V[idx][1]
 
    # Return Answer
    return res
 
# Driver Code
if __name__ == "__main__":
 
    arr = [[1, 4],
           [3, 4],
           [2, 3]]
 
    for x in closestInterval(arr, len(arr)):
        print(x, end=" ")
 
    # This code is contributed by rakeshsahni

-1 -1 1 

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)