Encuentre la distancia entre dos personas después de la reconstrucción de la cola

Dada una array 2D de tamaño N que contiene distintas alturas de las personas que están en una cola, y un número correspondiente a cada persona (P) que da el número de personas que son más bajas que P y están paradas frente a P. La tarea es determinar la distancia entre dos personas A y B en el orden real de la altura de las personas.
Ejemplo: 
 

Entrada: A = 6, B = 5, arr[][] = {{5, 0}, {3, 0}, {2, 0}, 
{6, 4}, {1, 0}, {4, 3}} 
Salida: 4 
Disposición real de la altura de las personas 
{5, 0}, {3, 0}, {2, 0}, {1, 0}, {6, 4}, {4, 3} 
Distancia entre 6 y 5 es 4
Entrada: A = 1, B = 3, arr[][] = {{3, 0}, {1, 0}, {2, 1}}; 
Salida: 1 
 

Enfoque ingenuo: un enfoque de fuerza bruta consiste en probar todas las permutaciones posibles de las alturas dadas del orden de los miembros del fénix y verificar si los números del frente coinciden con la secuencia dada, luego encontrar la distancia entre dos personas. 
Complejidad de tiempo: O(N!)
Enfoque eficiente: otro enfoque es almacenar la altura de la persona y su valor frontal, almacenarlo en cualquier vector y ordenar el vector según las alturas en orden ascendente. Ahora, atraviese el vector e inserte la persona en la posición k-ésima en el vector de posición donde k es el número de personas que están de pie frente a las personas de la persona actual.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the correct order and then
// return the distance between the two persons
int getDistance(int arr[][2], int n, int a, int b)
{
    vector<pair<int, int> > vp;
 
    // Make pair of both height & infront
    // and insert to vector
    for (int i = 0; i < n; i++) {
        vp.push_back({ arr[i][0], arr[i][1] });
    }
 
    // Sort the vector in ascending order
    sort(vp.begin(), vp.end());
 
    // Find the correct place for every person
    vector<int> pos;
 
    // Insert into position vector
    // according to infront value
    for (int i = 0; i < vp.size(); i++) {
        int height = vp[i].first;
        int k = vp[i].second;
        pos.insert(pos.begin() + k, height);
    }
 
    int first = -1, second = -1;
 
    for (int i = 0; i < pos.size(); i++) {
        if (pos[i] == a)
            first = i;
        if (pos[i] == b)
            second = i;
    }
 
    return abs(first - second);
}
 
// Driver code
int main()
{
    int arr[][2] = {
        { 5, 0 },
        { 3, 0 },
        { 2, 0 },
        { 6, 4 },
        { 1, 0 },
        { 4, 3 }
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    int a = 6, b = 5;
 
    cout << getDistance(arr, n, a, b);
 
    return 0;
}

# Python implementation of the approach
 
# Function to find the correct order and then
# return the distance between the two persons
def getDistance(arr, n, a, b):
    vp = []
 
    # Make pair of both height & infront
    # and insert to vector
    for i in range(n):
        vp.append([arr[i][0], arr[i][1]])
 
    # Sort the vector in ascending order
    vp = sorted(vp)
 
    # Find the correct place for every person
    pos = [0 for i in range(n)]
 
    # Insert into position vector
    # according to infront value
    for i in range(len(vp)):
        height = vp[i][0]
        k = vp[i][1]
        pos[k] = height
 
    first = -1
    second = -1
 
    for i in range(n):
        if (pos[i] == a):
            first = i
        if (pos[i] == b):
            second = i
 
    return abs(first - second)
 
# Driver code
arr = [[5, 0],
        [3, 0],
        [2, 0],
        [6, 4],
        [1, 0],
        [4, 3]]
n = len(arr)
a = 6
b = 5
 
print(getDistance(arr, n, a, b))
 
# This code is contributed by mohit kumar 29

<script>
// Javascript implementation of the approach
 
// Function to find the correct order and then
// return the distance between the two persons   
function getDistance(arr,n,a,b)
{
    let vp=[];
    // Make pair of both height & infront
    // and insert to vector
    for (let i = 0; i < n; i++) {
        vp.push([ arr[i][0], arr[i][1] ]);
    }
   
    // Sort the vector in ascending order
    vp.sort(function(c,d){return c[0]-d[0];});
   
    // Find the correct place for every person
    let pos=new Array(n);
    for(let i=0;i<n;i++)
    {
        pos[i]=0;
    }
       
    // Insert into position vector
    // according to infront value
    for (let i = 0; i < vp.length; i++) {
        let height = vp[i][0];
        let k = vp[i][1];
        pos[k] = height
    }
   
    let first = -1, second = -1;
   
    for (let i = 0; i < pos.length; i++) {
        if (pos[i] == a)
            first = i;
        if (pos[i] == b)
            second = i;
    }
   
    return Math.abs(first - second);
}
 
// Driver code
let arr = [
        [ 5, 0 ],
        [ 3, 0 ],
        [ 2, 0 ],
        [ 6, 4 ],
        [ 1, 0 ],
        [ 4, 3 ]
    ];
    let n = arr.length;
    let a = 6, b = 5;
   
    document.write(getDistance(arr, n, a, b));
 
// This code is contributed by unknown2108
</script>

4

Complejidad temporal: O(n ² )