Dada una array arr[] que consta de N enteros, donde el i -ésimo elemento representa el rango de un aspersor, es decir , [i-arr[i], i+arr[i]] que puede regar, la tarea es encontrar el número mínimo del rociador a encender para regar todas las plantas de la galería. Si no es posible regar todas las plantas, imprima -1.
Nota: Si arr[i] = -1 , entonces el rociador no se puede encender.
Ejemplos:
Entrada: arr[ ] = {-1, 2, 2, -1, 0, 0}
Salida: 2
Explicación:
Una de las formas posibles es:
- Encienda el rociador en el índice 2, puede regar las plantas en el rango [0, 4].
- Encienda el rociador en el índice 5, puede regar las plantas en el rango [5, 5].
Por lo tanto, encender dos aspersores puede regar todas las plantas. Además, es el número mínimo posible de rociadores a encender.
Entrada: array[ ] = {2, 3, 4, -1, 2, 0, 0, -1, 0}
Salida: -1
Enfoque: el problema anterior se puede resolver utilizando la técnica codiciosa . La idea es ordenar primero el rango por el límite izquierdo y luego atravesar los rangos desde la izquierda y en cada iteración seleccionar el límite más a la derecha que un aspersor puede cubrir teniendo el límite izquierdo en el rango actual. Siga los pasos a continuación para resolver el problema:
- Inicialice un vector<pair<int, int>> digamos V para almacenar el rango de cada aspersor como un par.
- Recorra la array arr[] y si arr[i] no es igual a -1 , empuje el par (i-arr[i], i+arr[i]) en el vector V .
- Ordena el vector de pares en orden ascendente por el primer elemento.
- Inicialice 2 variables, digamos res y maxRight para almacenar los rociadores mínimos que se encenderán y para almacenar el límite más a la derecha de una array.
- Inicialice una variable, digamos i como 0 para iterar sobre la V.
- Iterar hasta que maxRight sea menor que N y realizar los siguientes pasos:
- Si i es igual a V.size() o V[i].first es mayor que maxRight , imprima -1 y devuelva .
- Guarde el límite derecho del rociador actual en la variable digamos currMax .
- Ahora itere hasta que i+1 sea menor que V.size() y V[i+1].primero sea menor o igual que maxRight luego, en cada iteración, incremente i en 1 y actualice currMax como currMax = max(currMax, V[ i].segundo).
- Si currMax es menor que maxRight , imprima -1 y devuelva .
- Actualice maxRight como maxRight = currMax+1 y luego aumente res y i en 1 .
- Finalmente, después de completar el paso anterior, imprima el 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 minimum number of
// sprinkler to be turned on
int minSprinklers(int arr[], int N)
{
// Stores the leftmost and rightmost
// point of every sprinklers
vector<pair<int, int> > V;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
if (arr[i] > -1) {
V.push_back(
pair<int, int>(i - arr[i], i + arr[i]));
}
}
// Sort the array sprinklers in
// ascending order by first element
sort(V.begin(), V.end());
// Stores the rightmost range
// of a sprinkler
int maxRight = 0;
// Stores minimum sprinklers
// to be turned on
int res = 0;
int i = 0;
// Iterate until maxRight is
// less than N
while (maxRight < N) {
// If i is equal to V.size()
// or V[i].first is greater
// than maxRight
if (i == V.size() || V[i].first > maxRight) {
return -1;
}
// Stores the rightmost boundary
// of current sprinkler
int currMax = V[i].second;
// Iterate until i+1 is less
// than V.size() and V[i+1].first
// is less than or equal to maxRight
while (i + 1 < V.size()
&& V[i + 1].first <= maxRight) {
// Increment i by 1
i++;
// Update currMax
currMax = max(currMax, V[i].second);
}
// If currMax is less than the maxRight
if (currMax < maxRight) {
// Return -1
return -1;
}
// Increment res by 1
res++;
// Update maxRight
maxRight = currMax + 1;
// Increment i by 1
i++;
}
// Return res as answer
return res;
}
// Drive code.
int main()
{
// Input
int arr[] = { -1, 2, 2, -1, 0, 0 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << minSprinklers(arr, N);
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class pair {
int x;
int y;
pair(int x1, int y1)
{
x = x1;
y = y1;
}
}
class GFG {
// Function to find minimum number of
// sprinkler to be turned on
static int minSprinklers(int arr[], int N)
{
// Stores the leftmost and rightmost
// point of every sprinklers
ArrayList<pair> V = new ArrayList<pair>();
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
if (arr[i] > -1) {
V.add(new pair(i - arr[i], i + arr[i]));
}
}
// Sort the array sprinklers in
// ascending order by first element
Collections.sort(V, new Comparator<pair>() {
@Override public int compare(pair p1, pair p2)
{
return p1.x - p2.x;
}
});
// Stores the rightmost range
// of a sprinkler
int maxRight = 0;
// Stores minimum sprinklers
// to be turned on
int res = 0;
int i = 0;
// Iterate until maxRight is
// less than N
while (maxRight < N) {
// If i is equal to V.size()
// or V[i].first is greater
// than maxRight
if (i == V.size() || V.get(i).x > maxRight) {
return -1;
}
// Stores the rightmost boundary
// of current sprinkler
int currMax = V.get(i).y;
// Iterate until i+1 is less
// than V.size() and V[i+1].first
// is less than or equal to maxRight
while (i + 1 < V.size()
&& V.get(i + 1).x <= maxRight) {
// Increment i by 1
i++;
// Update currMax
currMax = Math.max(currMax, V.get(i).y);
}
// If currMax is less than the maxRight
if (currMax < maxRight) {
// Return -1
return -1;
}
// Increment res by 1
res++;
// Update maxRight
maxRight = currMax + 1;
// Increment i by 1
i++;
}
// Return res as answer
return res;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { -1, 2, 2, -1, 0, 0 };
int N = 6;
// Function call
System.out.println(minSprinklers(arr, N));
}
}
// This code is contributed by Manu Pathria
Python3
# Python program for the above approach # Function to find minimum number of # sprinkler to be turned on def minSprinklers(arr, N): # Stores the leftmost and rightmost # point of every sprinklers V = [] # Traverse the array arr[] for i in range(N): if (arr[i] > -1): V.append([i - arr[i], i + arr[i]]) # Sort the array sprinklers in # ascending order by first element V.sort() # Stores the rightmost range # of a sprinkler maxRight = 0 # Stores minimum sprinklers # to be turned on res = 0 i = 0 # Iterate until maxRight is # less than N while (maxRight < N): # If i is equal to V.size() # or V[i][0] is greater # than maxRight if (i == len(V) or V[i][0] > maxRight): return -1 # Stores the rightmost boundary # of current sprinkler currMax = V[i][1] # Iterate until i+1 is less # than V.size() and V[i+1][0] # is less than or equal to maxRight while (i + 1 < len(V) and V[i + 1][0] <= maxRight): # Increment i by 1 i += 1 # Update currMax currMax = max(currMax, V[i][1]) # If currMax is less than the maxRight if (currMax < maxRight): # Return -1 return -1 # Increment res by 1 res += 1 # Update maxRight maxRight = currMax + 1 # Increment i by 1 i += 1 # Return res as answer return res # Drive code. # Input arr = [-1, 2, 2, -1, 0, 0] N = len(arr) # Function call print(minSprinklers(arr, N)) # This code is contributed by _saurabh_jaiswal.
Javascript
<script>
// JavaScript program for the above approach
// Function to find minimum number of
// sprinkler to be turned on
function minSprinklers(arr, N) {
// Stores the leftmost and rightmost
// point of every sprinklers
let V = [];
// Traverse the array arr[]
for (let i = 0; i < N; i++) {
if (arr[i] > -1) {
V.push([i - arr[i], i + arr[i]]);
}
}
// Sort the array sprinklers in
// ascending order by first element
V.sort((a, b) => a - b);
// Stores the rightmost range
// of a sprinkler
let maxRight = 0;
// Stores minimum sprinklers
// to be turned on
let res = 0;
let i = 0;
// Iterate until maxRight is
// less than N
while (maxRight < N) {
// If i is equal to V.size()
// or V[i][0] is greater
// than maxRight
if (i == V.length || V[i][0] > maxRight) {
return -1;
}
// Stores the rightmost boundary
// of current sprinkler
let currMax = V[i][1];
// Iterate until i+1 is less
// than V.size() and V[i+1][0]
// is less than or equal to maxRight
while (i + 1 < V.length
&& V[i + 1][0] <= maxRight) {
// Increment i by 1
i++;
// Update currMax
currMax = Math.max(currMax, V[i][1]);
}
// If currMax is less than the maxRight
if (currMax < maxRight) {
// Return -1
return -1;
}
// Increment res by 1
res++;
// Update maxRight
maxRight = currMax + 1;
// Increment i by 1
i++;
}
// Return res as answer
return res;
}
// Drive code.
// Input
let arr = [-1, 2, 2, -1, 0, 0];
let N = arr.length;
// Function call
document.write(minSprinklers(arr, N));
</script>
Producción:
2
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por nareshsaharan1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA