Dadas N cajas y su tamaño en una array. Se le permite mantener una caja dentro de otra caja solo si la caja en la que se guarda está vacía y el tamaño de la caja es al menos el doble del tamaño de la caja. La tarea es encontrar el número mínimo de cajas visibles.
Ejemplos:
Input : arr[] = { 1, 3, 4, 5 }
Output : 3
Put box of size 1 in box of size 3.
Input : arr[] = { 4, 2, 1, 8 }
Output : 1
Put box of size 1 in box of size 2
and box of size 2 in box of size 4.
And put box of size 4 in box of size 8.
La idea es ordenar la array. Ahora, haga una cola e inserte el primer elemento de la array ordenada. Ahora recorra la array desde el primer elemento e inserte cada elemento en la cola, también verifique si el elemento frontal de la cola es menor o igual a la mitad del elemento atravesado actual. Entonces, el número de cuadros visibles será el número de elementos en la cola después de atravesar la array ordenada. Básicamente, estamos tratando de poner una caja de tamaño en la caja más pequeña que sea mayor o igual a 2*x.
Por ejemplo, si arr[] = { 2, 3, 4, 6 }, entonces intentamos poner el cuadro de tamaño 2 en el cuadro de tamaño 4 en lugar del cuadro de tamaño 6 porque si ponemos el cuadro de tamaño 2 en el cuadro de tamaño 6, entonces el cuadro de tamaño 3 no se puede guardar en ningún otro cuadro y debemos minimizar el número de cuadros visibles.
Implementación:
C++
// CPP program to count number of visible boxes.
#include <bits/stdc++.h>
using namespace std;
// return the minimum number of visible boxes
int minimumBox(int arr[], int n)
{
queue<int> q;
// sorting the array
sort(arr, arr + n);
q.push(arr[0]);
// traversing the array
for (int i = 1; i < n; i++) {
int now = q.front();
// checking if current element
// is greater than or equal to
// twice of front element
if (arr[i] >= 2 * now)
q.pop();
// Pushing each element of array
q.push(arr[i]);
}
return q.size();
}
// driver Program
int main()
{
int arr[] = { 4, 1, 2, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << minimumBox(arr, n) << endl;
return 0;
}
Java
// Java program to count number of visible
// boxes.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Arrays;
public class GFG {
// return the minimum number of visible
// boxes
static int minimumBox(int []arr, int n)
{
// New Queue of integers.
Queue<Integer> q = new LinkedList<>();
// sorting the array
Arrays.sort(arr);
q.add(arr[0]);
// traversing the array
for (int i = 1; i < n; i++)
{
int now = q.element();
// checking if current element
// is greater than or equal to
// twice of front element
if (arr[i] >= 2 * now)
q.remove();
// Pushing each element of array
q.add(arr[i]);
}
return q.size();
}
// Driver code
public static void main(String args[])
{
int [] arr = { 4, 1, 2, 8 };
int n = arr.length;
System.out.println(minimumBox(arr, n));
}
}
// This code is contributed by Sam007.
Python3
# Python3 program to count number # of visible boxes. import collections # return the minimum number of visible boxes def minimumBox(arr, n): q = collections.deque([]) # sorting the array arr.sort() q.append(arr[0]) # traversing the array for i in range(1, n): now = q[0] # checking if current element # is greater than or equal to # twice of front element if(arr[i] >= 2 * now): q.popleft() # Pushing each element of array q.append(arr[i]) return len(q) # driver Program if __name__=='__main__': arr = [4, 1, 2, 8 ] n = len(arr) print(minimumBox(arr, n)) # This code is contributed by # Sanjit_Prasad
C#
// C# program to count number of visible
// boxes.
using System;
using System.Collections.Generic;
class GFG {
// return the minimum number of visible
// boxes
static int minimumBox(int []arr, int n)
{
// New Queue of integers.
Queue<int> q = new Queue<int>();
// sorting the array
Array.Sort(arr);
q.Enqueue(arr[0]);
// traversing the array
for (int i = 1; i < n; i++)
{
int now = q.Peek();
// checking if current element
// is greater than or equal to
// twice of front element
if (arr[i] >= 2 * now)
q.Dequeue();
// Pushing each element of array
q.Enqueue(arr[i]);
}
return q.Count;
}
// Driver code
public static void Main()
{
int [] arr = { 4, 1, 2, 8 };
int n = arr.Length;
Console.WriteLine(minimumBox(arr, n));
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to count number of visible boxes.
// return the minimum number of visible boxes
function minimumBox($arr, $n)
{
$q = array();
// sorting the array
sort($arr);
array_push($q, $arr[0]);
// traversing the array
for ($i = 1; $i < $n; $i++)
{
$now = $q[0];
// checking if current element
// is greater than or equal to
// twice of front element
if ($arr[$i] >= 2 * $now)
array_pop($q);
// Pushing each element of array
array_push($q,$arr[$i]);
}
return count($q);
}
// Driver Code
$arr = array( 4, 1, 2, 8 );
$n = count($arr);
echo minimumBox($arr, $n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to count
// number of visible boxes.
// return the minimum number
// of visible boxes
function minimumBox(arr, n)
{
var q = [];
// sorting the array
arr.sort((a,b)=> a-b)
q.push(arr[0]);
// traversing the array
for (var i = 1; i < n; i++) {
var now = q[0];
// checking if current element
// is greater than or equal to
// twice of front element
if (arr[i] >= 2 * now)
q.pop(0);
// Pushing each element of array
q.push(arr[i]);
}
return q.length;
}
// driver Program
var arr = [ 4, 1, 2, 8 ];
var n = arr.length;
document.write( minimumBox(arr, n));
</script>
1
Complejidad de tiempo: O (nlogn)