Encuentre el elemento con el peso máximo en el rango de precios dado para las consultas Q

Dada una array arr[] de tamaño N donde cada elemento denota un par en la forma (precio, peso) que denota el precio y el peso de cada artículo. Consultas Q dadas de la forma [X, Y] que denotan el rango de precios. La tarea es encontrar el elemento con mayor peso dentro de un rango de precio determinado para cada consulta. 

Ejemplos: 

Entrada: arr[][] = {{24, 6}, {30, 8}, {21, 7}},  
consultas[][] = {{10, 24}, {20, 30}} 
Salida: [ 7, 8]
Explicación: Los siguientes son los elementos elegidos para el rango anterior
 Para la primera consulta: Hay dos elementos con el rango dado [10, 24] -> {24, 6} y {21, 7}. El peso más alto es 7.
 Para la segunda consulta: hay dos elementos con un rango determinado [20, 30] -> {24, 6}, {21, 7} y {30, 8}. El peso más alto es 8.
Por lo tanto, la respuesta es [7, 8].

Entrada: arr[][] = {{1000, 300}, {1100, 400}, {1300, 200}, {1700, 500}, {2000, 600}},  
consultas[][] = {{1000, 1400}, {1700, 500}, {2000, 600}}
Salida: [400, 500, 600]

Enfoque ingenuo: una solución simple es ejecutar un ciclo para el rango de precios y encontrar el peso máximo para cada consulta. 

Complejidad temporal: O(Q*N).
Espacio Auxiliar: O(1)

Enfoque eficiente: un enfoque eficiente es preprocesar para almacenar el peso máximo en el rango de precios [i, j] para cualquier i y j. Utilice el árbol de segmentos para el preprocesamiento y la consulta en un tiempo moderado.

Representación de árboles de segmentos

1. Los Nodes hoja son el peso correspondiente a los elementos de la array de entrada.
2. Cada Node interno representa el peso máximo de todas las hojas debajo de él.

Se utiliza una representación de array de un árbol para representar árboles de segmento. Para cada Node en el índice i , el hijo izquierdo está en el índice 2*i+1 , el hijo derecho está en 2*i+2 y el padre está en ⌊(i – 1) / 2⌋ .

La solución se puede elaborar dividiendo el enfoque en dos partes:

1. Construcción del árbol de segmentos a partir de la array dada: 

   • Comience con un segmento [0 . . . N-1] . y cada vez divida el segmento actual en dos mitades (si aún no se ha convertido en un segmento de longitud 1).
   • Luego llame al mismo procedimiento en ambas mitades y, para cada segmento, almacene el valor máximo en un Node de árbol de segmento. 
     Cada Node aquí representa el peso máximo para el rango de precios dado entre índices de segmento dados.

   Nota: Todos los niveles del árbol de segmentos construido se llenarán por completo excepto el último nivel. Además, el árbol será un árbol binario completo porque los segmentos se dividen en dos mitades en cada nivel. Dado que el árbol construido es siempre un árbol binario completo con N hojas.

2. La consulta por el valor mínimo del rango dado: una vez que se construye el árbol, cómo hacer una consulta de rango máximo usando el árbol de segmento construido. El siguiente es el algoritmo para obtener el máximo.

   • Si el rango de precios del Node es el mismo que el rango de precios dado de la consulta, devuelva el valor en el Node.
   • Si el rango está completamente fuera del rango dado, devuelva un valor extremadamente alto o diga un valor infinito.
   • De lo contrario, llame a una función recursiva para los niños izquierdo y derecho y devuelva el máximo recibido de las llamadas recursivas.

Vea la imagen a continuación para comprender la formación del árbol de segmentos para una entrada determinada.

Representación de imagen del árbol de segmentos para la entrada dada

Consulte el siguiente algoritmo para una mejor comprensión.

// qs –> consultar precio inicial, qe –> consultar precio final

int RMQ(node, qs, qe)
{
 si el rango de precios del Node está dentro de qs y qe
       devuelve el valor en el Node ; de
 lo contrario, si el rango de precios del Node está completamente fuera de qs y qe,
      devuelve INFINITO ; de
lo contrario,
   devuelve max( RMQ(hijo izquierdo del Node, qs, qe), RMQ(hijo derecho del Node, qs, qe) )
}

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

// Java code to implement above approach
import java.io.*;
import java.util.*;
  
class GFG {
    static int[] segmentTree;
  
    // Function to get mid
    public static int getMid(int start,
                             int end)
    {
        return start + (end - start) / 2;
    }
  
    // Function to fill segment tree
    public static void fillSegmentTree(int[][] arr)
    {
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1,
                               int[] o2)
            {
                return o1[0] - o2[0];
            }
        });
  
        int n = arr.length;
        int maxHeight
            = (int)Math.ceil(Math.log(n)
                             / Math.log(2));
        int maxSize
            = 2 * (int)Math.pow(2, maxHeight) - 1;
        segmentTree = new int[maxSize];
  
        fillSegmentTreeUtil(segmentTree, arr,
                            0, n - 1, 0);
    }
  
    // Function to utilise the segment tree
    public static int
    fillSegmentTreeUtil(int[] segmentTree,
                        int[][] arr,
                        int start, int end,
                        int currNode)
    {
        if (start == end) {
            segmentTree[currNode]
                = arr[start][1];
            return segmentTree[currNode];
        }
  
        int mid = getMid(start, end);
        segmentTree[currNode] = Math.max(
            fillSegmentTreeUtil(segmentTree,
                                arr, start,
                                mid, currNode
                                             * 2
                                         + 1),
            fillSegmentTreeUtil(segmentTree,
                                arr, mid + 1,
                                end, currNode
                                             * 2
                                         + 2));
        return segmentTree[currNode];
    }
  
    // Function to find the maximum rating
    public static int findMaxRating(int[][] arr,
                                    int[] query)
    {
        int n = arr.length;
        return findMaxRatingUtil(segmentTree,
                                 arr, 0, n - 1,
                                 query[0],
                                 query[1], 0);
    }
  
    // Function to utilise the
    // maxRating function
    public static int
    findMaxRatingUtil(int[] segmentTree,
                      int[][] arr,
                      int start, int end,
                      int qStart,
                      int qEnd, int currNode)
    {
        if (qStart <= arr[start][0]
            && qEnd >= arr[end][0]) {
            return segmentTree[currNode];
        }
        if (qStart > arr[end][0] || qEnd < arr[start][0]) {
            return -1;
        }
        int mid = getMid(start, end);
        return Math.max(
            findMaxRatingUtil(segmentTree,
                              arr, start, mid,
                              qStart, qEnd,
                              currNode * 2 + 1),
            findMaxRatingUtil(segmentTree,
                              arr, mid + 1,
                              end, qStart, qEnd,
                              currNode * 2 + 2));
    }
  
    // Driver code
    public static void main(String[] args)
    {
        int[][] arr = { { 1000, 300 },
                        { 1100, 400 },
                        { 1300, 200 },
                        { 1700, 500 },
                        { 2000, 600 } };
  
        fillSegmentTree(arr);
  
        int[][] queries = { { 1000, 1400 },
                            { 1700, 1900 },
                            { 0, 3000 } };
  
        for (int[] query : queries) {
            System.out.println(
                findMaxRating(arr, query));
        }
    }
}

400
500
600

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

Análisis de la complejidad del tiempo: La complejidad del tiempo para ordenar la array de entrada dada es O(N * LogN)
La complejidad del tiempo para la construcción del árbol es O(N) . Hay un total de 2N-1 Nodes, y el valor de cada Node se calcula solo una vez en la construcción del árbol.
La complejidad de tiempo para cada consulta es O(LogN) . Para consultar un rango máximo, procese como máximo dos Nodes en cada nivel, y el número de niveles es O(LogN) . 

Tema relacionado: Árbol de segmentos