Dada una array Intervals[] que consta de N pares de enteros donde cada par denota el rango de valores [L, R] . Además, dada una array de enteros Q[] que consta de M consultas. Para cada consulta, la tarea es encontrar el tamaño del rango más pequeño que contiene ese elemento. Retorna -1 si no existe un intervalo válido.
Ejemplos
Entrada: Intervalos[] = [[1, 4], [2, 3], [3, 6], [9, 25], [7, 15], [4, 4]]
Q[] = [7, 50, 2]
Salida: [9, -1, 2]
Explicación: El elemento 7 está en el rango [7, 15] solo que, por lo tanto, la respuesta será 15 – 7 + 1 = 9. El elemento 50 no está en el rango. Por lo tanto, la respuesta será -1.
De manera similar, el elemento 2 está en el rango [2, 3] y [1, 4] pero el rango más pequeño es [2, 3], por lo tanto, la respuesta será 3-2+1 = 2.Entrada: Intervalos[] = [[1, 4], [2, 4], [3, 6]]
Q[] = [2, 3]
Salida: [3, 3]
Enfoque ingenuo: el enfoque más simple para resolver el problema es iterar a través del rango de array [] y para cada consulta encontrar el rango más pequeño que contiene los elementos dados.
Complejidad temporal: O(N×M)
Espacio auxiliar: O(M)
Enfoque eficiente: el enfoque mencionado anteriormente se puede optimizar aún más mediante el uso de priority_queue . Siga los pasos a continuación para resolver el problema:
- Inicialice un vector de vectores, diga Consultas e inserte todas las consultas en la array Q junto con su índice.
- Ordene los Intervalos y Consultas del vector utilizando la función de clasificación predeterminada del vector .
- Inicialice una cola de prioridad , digamos pq con clave como el tamaño de Intervalo y valor como límite derecho del rango.
- Inicialice un vector , digamos resultado que almacenará el tamaño del rango mínimo para cada consulta.
- Inicialice una variable entera, digamos i , que mantendrá el seguimiento de los elementos recorridos de la array Intervals .
- Iterar en el rango [0, M-1] usando la variable j y realizar los siguientes pasos:
- Iterar while i < Intervalos.tamaño() e Intervalos[i][0] <= Consultas[j][0] , insertar -(Intervalos[i][1] – Intervalos[i][0] + 1), Intervalos [i][1] como par e incrementa el valor de i en 1 .
- Ahora elimine todos los elementos de la cola de prioridad pq con el elemento correcto menor que Consultas[j][0] .
- Si el tamaño de la cola de prioridad pq>0 , modifique el valor de result[Queries[j][1]] como pq.top()[0] .
- Devuelve la array res[] como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the size of minimum // Interval that contains the given element vector<int> minInterval(vector<vector<int> >& intervals, vector<int>& q) { // Store all the queries // along with their index vector<vector<int> > queries; for (int i = 0; i < q.size(); i++) queries.push_back({ q[i], i }); // Sort the vector intervals and queries sort(intervals.begin(), intervals.end()); sort(queries.begin(), queries.end()); // Max priority queue to keep track // of intervals size and right value priority_queue<vector<int> > pq; // Stores the result of all the queries vector<int> result(queries.size(), -1); // Current position of intervals int i = 0; for (int j = 0; j < queries.size(); j++) { // Stores the current query int temp = queries[j][0]; // Insert all the intervals whose left value // is less than or equal to the current query while (i < intervals.size() && intervals[i][0] <= temp) { // Insert the negative of range size and // the right bound of the interval pq.push( { -intervals[i][1] + intervals[i][0] - 1, intervals[i++][1] }); } // Pop all the intervals with right value // less than the current query while (!pq.empty() && temp > pq.top()[1]) { pq.pop(); } // Check if the valid interval exists // Update the answer for current query // in result array if (!pq.empty()) result[queries[j][1]] = -pq.top()[0]; } // Return the result array return result; } // Driver Code int main() { // Given Input vector<vector<int> > intervals = { { 1, 4 }, { 2, 3 }, { 3, 6 }, { 9, 25 }, { 7, 15 }, { 4, 4 } }; vector<int> Q = { 7, 50, 2, 3, 4, 9 }; // Function Call vector<int> result = minInterval(intervals, Q); // Print the result for each query for (int i = 0; i < result.size(); i++) cout << result[i] << " "; return 0; }
Javascript
<script> // Javascript program for the above approach // Function to find the size of minimum // Interval that contains the given element function minInterval(intervals, q) { // Store all the queries // along with their index var queries = []; for (var i = 0; i < q.length; i++) queries.push([q[i], i]); // Sort the vector intervals and queries intervals.sort((a,b)=> { if(a[0] == b[0]) return a[1] - b[1]; return a[0] - b[0]; }); queries.sort((a,b)=> { if(a[0] == b[0]) return a[1]-b[1]; return a[0]-b[0]; }); // Max priority queue to keep track // of intervals size and right value var pq = []; // Stores the result of all the queries var result = Array(queries.length).fill(-1); // Current position of intervals var i = 0; for (var j = 0; j < queries.length; j++) { // Stores the current query var temp = queries[j][0]; // Insert all the intervals whose left value // is less than or equal to the current query while (i < intervals.length && intervals[i][0] <= temp) { // Insert the negative of range size and // the right bound of the interval pq.push( [ -intervals[i][1] + intervals[i][0] - 1, intervals[i++][1] ]); } pq.sort((a,b)=> { if(a[0] == b[0]) return a[1]-b[1]; return a[0]-b[0]; }); // Pop all the intervals with right value // less than the current query while (pq.length != 0 && temp > pq[pq.length-1][1]) { pq.pop(); } // Check if the valid interval exists // Update the answer for current query // in result array if (pq.length!=0) result[queries[j][1]] = -pq[pq.length-1][0]; } // Return the result array return result; } // Driver Code // Given Input var intervals = [ [ 1, 4 ], [ 2, 3 ], [ 3, 6 ], [ 9, 25 ], [ 7, 15 ], [ 4, 4 ] ]; var Q = [ 7, 50, 2, 3, 4, 9 ]; // Function Call var result = minInterval(intervals, Q); // Print the result for each query for (var i = 0; i < result.length; i++) document.write(result[i] + " "); // This code is contributed by rrrtnx. </script>
9 -1 2 2 1 9
Complejidad de tiempo: O(NlogN+MlogM)
Espacio auxiliar : O(N+M)