Dada una array points[][] de tamaño N , donde points[i] representa un globo sobre el área de coordenadas X desde points[i][0] hasta points[i][1] . Las coordenadas Y no importan. Se requiere que todos los globos sean reventados. Para reventar un globo, se puede lanzar una flecha en el punto (x, 0) y viaja verticalmente hacia arriba y reventa todos los globos que cumplen la condición puntos[i][0] <= x <= puntos[i][1] . La tarea es encontrar el número mínimo de flechas necesarias para reventar todos los globos.
Ejemplos:
Entrada: N = 4, puntos = {{10, 16}, {2, 8}, {1, 6}, {7, 12}}
Salida: 2
Explicación: una forma es disparar una flecha, por ejemplo, a x = 6 (reventar los globos [2, 8] y [1, 6]) y otra flecha en x = 11 (reventar los otros dos globos).Entrada: N = 1, puntos = {{1, 6}}
Salida: 1
Explicación: Una sola flecha puede reventar el globo.
Enfoque: El problema dado se puede resolver utilizando el Enfoque codicioso para encontrar los globos que se superponen entre sí para que la flecha pueda atravesar todos esos globos y reventarlos. Para hacerlo de manera óptima, ordene la array con respecto a la coordenada X en orden ascendente . Entonces, ahora considere 2 globos, si el segundo globo comienza antes que el primer globo, entonces debe terminar después del primer globo o en la misma posición.
Por ejemplo [1, 6], [2, 8] -> la posición inicial del segundo globo, es decir, 2, que está antes de la posición final del primer globo, es decir, 6, y dado que la array está ordenada, el final del segundo globo siempre es mayor que el final del primer globo. El segundo extremo del globo, es decir, 8, está después del final del primer globo, es decir, 6, lo que nos muestra que la superposición existe entre [2, 6].
Siga los pasos a continuación para resolver el problema:
- Ordene la array según la posición final de los globos usando la expresión comparator/lambda Arrays.sort(points, (a, b)-> Integer.compare(a[1], b[1])) .
- Haga una flecha variable e inicialícela con 1 (como mínimo se necesitará una flecha para reventar los globos)
- Haz un final variable e inicialízalo con los puntos [0] [1] que almacenarán el final del primer globo.
- Itere sobre el rango [1, N) usando la variable i y realice los siguientes pasos:
- Compruebe si el inicio de los siguientes puntos de globo [i][0] es menor que la variable final end .
- Si es así, continúe con la iteración.
- De lo contrario, aumente el recuento de la flecha en 1 y establezca el valor de end como points[i][1] .
- Después de completar los pasos anteriores, imprima el valor de la flecha como el conteo resultante de flechas requeridas.
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;
bool cmp(vector<int> a, vector<int> b)
{
return b[1] > a[1];
}
// Function to find the minimum count of
// arrows required to burst all balloons
int minArrows(vector<vector<int>> points)
{
// To sort our array according
// to end position of balloons
sort(points.begin(), points.end(), cmp);
// Initialize end variable with
// the end of first balloon
int end = points[0][1];
// Initialize arrow with 1
int arrow = 1;
// Iterate through the entire
// arrow of points
for (int i = 1; i < points.size(); i++)
{
// If the start of ith balloon
// <= end than do nothing
if (points[i][0] <= end)
{
continue;
}
// if start of the next balloon
// >= end of the first balloon
// then increment the arrow
else
{
// Update the new end
end = points[i][1];
arrow++;
}
}
// Return the total count of arrows
return arrow;
}
// Driver code
int main()
{
vector<vector<int>> points = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
cout << (minArrows(points));
return 0;
}
// This code is contributed by Potta Lokesh
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the minimum count of
// arrows required to burst all balloons
public static int minArrows(int points[][])
{
// To sort our array according
// to end position of balloons
Arrays.sort(points,
(a, b) -> Integer.compare(a[1], b[1]));
// Initialize end variable with
// the end of first balloon
int end = points[0][1];
// Initialize arrow with 1
int arrow = 1;
// Iterate through the entire
// arrow of points
for (int i = 1; i < points.length; i++) {
// If the start of ith balloon
// <= end than do nothing
if (points[i][0] <= end) {
continue;
}
// if start of the next balloon
// >= end of the first balloon
// then increment the arrow
else {
// Update the new end
end = points[i][1];
arrow++;
}
}
// Return the total count of arrows
return arrow;
}
// Driver Code
public static void main(String[] args)
{
int[][] points
= { { 10, 16 }, { 2, 8 }, { 1, 6 }, { 7, 12 } };
System.out.println(
minArrows(points));
}
}
Python3
# Python3 program for the above approach # Function to find the minimum count of # arrows required to burst all balloons def minArrows(points): # To sort our array according # to end position of balloons points = sorted(points, key = lambda x:x[1]) # Initialize end variable with # the end of first balloon end = points[0][1]; # Initialize arrow with 1 arrow = 1; # Iterate through the entire # arrow of points for i in range (1, len(points)) : # If the start of ith balloon # <= end than do nothing if (points[i][0] <= end) : continue; # if start of the next balloon # >= end of the first balloon # then increment the arrow else : # Update the new end end = points[i][1] arrow = arrow + 1 # Return the total count of arrows return arrow; # Driver Code points = [[10, 16 ], [ 2, 8 ], [1, 6 ], [ 7, 12 ]] print(minArrows(points)) # This code is contributed by AR_Gaurav
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the minimum count of
// arrows required to burst all balloons
public static int minArrows(int[][] points)
{
// To sort our array according
// to end position of balloons
// Array.Sort(points, (a, b) => {return a[1] - b[1];});
Comparer<int> comparer = Comparer<int>.Default;
Array.Sort<int[]>(points, (x,y) => comparer.Compare(x[1],y[1]));
// Initialize end variable with
// the end of first balloon
int end = points[0][1];
// Initialize arrow with 1
int arrow = 1;
// Iterate through the entire
// arrow of points
for (int i = 1; i < points.Length; i++) {
// If the start of ith balloon
// <= end than do nothing
if (points[i][0] <= end) {
continue;
}
// if start of the next balloon
// >= end of the first balloon
// then increment the arrow
else {
// Update the new end
end = points[i][1];
arrow++;
}
}
// Return the total count of arrows
return arrow;
}
// Driver Code
public static void Main(String[] args)
{
int[][] points
= { new int[] { 10, 16 }, new int[] { 2, 8 }, new int[]{ 1, 6 }, new int[]{ 7, 12 } };
Console.Write(minArrows(points));
}
}
// This code is contributed by saurabh_jaiswal.
Javascript
<script>
// Javascript program for the above approach
function cmp(a, b) {
return a[1] - b[1];
}
// Function to find the minimum count of
// arrows required to burst all balloons
function minArrows(points)
{
// To sort our array according
// to end position of balloons
points.sort(cmp);
// Initialize end variable with
// the end of first balloon
let end = points[0][1];
// Initialize arrow with 1
let arrow = 1;
// Iterate through the entire
// arrow of points
for (let i = 1; i < points.length; i++) {
// If the start of ith balloon
// <= end than do nothing
if (points[i][0] <= end) {
continue;
}
// if start of the next balloon
// >= end of the first balloon
// then increment the arrow
else {
// Update the new end
end = points[i][1];
arrow++;
}
}
// Return the total count of arrows
return arrow;
}
// Driver code
let points = [
[10, 16],
[2, 8],
[1, 6],
[7, 12],
];
document.write(minArrows(points));
// This code is contributed by gfgking.
</script>
2
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)