Número máximo de sobres que se pueden poner dentro de otros sobres más grandes

Posted on by Rudeus Greyrat

Dado N número de sobres, como par {W, H} , donde W es el ancho y H la altura. Un sobre puede caber en otro si y solo si tanto el ancho como el alto de un sobre son mayores que el ancho y el alto del otro sobre. Encuentre el número máximo de sobres que se pueden poner dentro de otro sobre y así sucesivamente. No se permite la rotación del sobre.

Ejemplos:

Entrada: sobre[] = {{4, 3}, {5, 3}, {5, 6}, {1, 2}}
Salida: 3
Explicación: 
El número máximo de sobres que se pueden poner en otro sobre 
es 3 (
{1, 2}, {4, 3}, {5, 6})

Entrada: envolvente[] = {{3, 6}, {5, 4}, {4, 8}, {6, 9}, {10, 7}, {12, 12}}
Salida: 4
Explicación:
El máximo número de sobres que se pueden poner en otro sobre es 4.
 ({3, 6}, {4, 8}, {6, 9}, {12, 12})

Enfoque ingenuo: este problema es similar al problema de la subsecuencia creciente más larga de la programación dinámica . La idea es clasificar los sobres en orden no decreciente y para cada sobre comprobar el número de sobres que se pueden poner dentro de ese sobre. Siga los pasos a continuación para resolver el problema:

  • Ordene la array en el orden no decreciente de ancho y alto.
  • Inicialice una array dp[] , donde dp[i] almacena la cantidad de sobres que se pueden colocar dentro con sobre[i] como el sobre más grande.
  • Para cada sobre[i], recorra los sobres más pequeños que él mismo y verifique si el ancho y la altura del sobre más pequeño son estrictamente menores que los del sobre[i]. Si es menor, el sobre más pequeño puede colocarse dentro del sobre[i].
  • El máximo de la array dp[] da el número máximo de sobres que se pueden poner uno dentro de otro.

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 that returns the maximum
// number of envelopes that can be
// inserted into another envelopes
int maxEnvelopes(vector<vector<int> > envelopes)
{
    // Number of envelopes
    int N = envelopes.size();
 
    if (N == 0)
        return N;
 
    // Sort the envelopes in
    // non-decreasing order
    sort(envelopes.begin(),
        envelopes.end());
 
    // Initialize dp[] array
    int dp[N];
 
    // To store the result
    int max_envelope = 1;
 
    dp[0] = 1;
 
    // Loop through the array
    for (int i = 1; i < N; ++i) {
        dp[i] = 1;
 
        // Find envelopes count for
        // each envelope
        for (int j = 0; j < i; ++j) {
 
            if (envelopes[i][0] > envelopes[j][0]
                && envelopes[i][1] > envelopes[j][1]
                && dp[i] < dp[j] + 1)
                dp[i] = dp[j] + 1;
        }
 
        // Store maximum envelopes count
        max_envelope = max(max_envelope,
                        dp[i]);
    }
 
    // Return the result
    return max_envelope;
}
 
// Driver Code
int main()
{
    // Given the envelopes
    vector<vector<int> > envelopes
        = { { 4, 3 }, { 5, 3 }, { 5, 6 }, { 1, 2 } };
 
    // Function Call
    cout << maxEnvelopes(envelopes);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
import java.lang.*;
 
class GFG{
     
// Function that returns the maximum
// number of envelopes that can be
// inserted into another envelopes
static int maxEnvelopes(int[][] envelopes)
{
     
    // Number of envelopes
    int N = envelopes.length;
     
    if (N == 0)
        return N;
     
    // Sort the envelopes in
    // non-decreasing order
    Arrays.sort(envelopes,
               (a, b) -> (a[0] != b[0]) ?
                          a[0] - b[0] :
                          a[1] - b[1]);
                           
    // Initialize dp[] array
    int[] dp = new int[N];
     
    // To store the result
    int max_envelope = 1;
     
    dp[0] = 1;
     
    // Loop through the array
    for(int i = 1; i < N; ++i)
    {
        dp[i] = 1;
         
        // Find envelopes count for
        // each envelope
        for(int j = 0; j < i; ++j)
        {
             
            if (envelopes[i][0] > envelopes[j][0] &&
                envelopes[i][1] > envelopes[j][1] &&
                          dp[i] < dp[j] + 1)
                dp[i] = dp[j] + 1;
        }
         
        // Store maximum envelopes count
        max_envelope = Math.max(max_envelope, dp[i]);
    }
     
    // Return the result
    return max_envelope;
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given the envelopes
    int[][] envelopes = { { 4, 3 }, { 5, 3 },
                          { 5, 6 }, { 1, 2 } };
     
    // Function call
    System.out.println(maxEnvelopes(envelopes));
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program for the above approach
 
# Function that returns the maximum
# number of envelopes that can be
# inserted into another envelopes
def maxEnvelopes(envelopes):
 
    # Number of envelopes
    N = len(envelopes)
 
    if (N == 0):
        return N
 
    # Sort the envelopes in
    # non-decreasing order
    envelopes = sorted(envelopes)
 
    # Initialize dp[] array
    dp = [0] * N
 
    # To store the result
    max_envelope = 1
 
    dp[0] = 1
 
    # Loop through the array
    for i in range(1, N):
        dp[i] = 1
 
        # Find envelopes count for
        # each envelope
        for j in range(i):
 
            if (envelopes[i][0] > envelopes[j][0]
                and envelopes[i][1] > envelopes[j][1]
                and dp[i] < dp[j] + 1):
                dp[i] = dp[j] + 1
 
        # Store maximum envelopes count
        max_envelope = max(max_envelope, dp[i])
 
    # Return the result
    return max_envelope
 
# Driver Code
if __name__ == '__main__':
 
    # Given the envelopes
    envelopes = [ [ 4, 3 ], [ 5, 3 ],
                [ 5, 6 ], [ 1, 2 ] ]
 
    # Function Call
    print(maxEnvelopes(envelopes))
 
# This code is contributed by Mohit Kumar

C#

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
    // Function that returns the maximum
    // number of envelopes that can be
    // inserted into another envelopes
    static int maxEnvelopes(int[][] envelopes)
    {
         
        // Number of envelopes
        int N = envelopes.Length;
         
        if (N == 0){
            return N;
        }
         
        // Sort the envelopes in
        // non-decreasing order
        Array.Sort(envelopes, new comp());
                             
        // Initialize dp[] array
        int[] dp = new int[N];
         
        // To store the result
        int max_envelope = 1;
         
        dp[0] = 1;
         
        // Loop through the array
        for(int i = 1 ; i < N ; ++i)
        {
            dp[i] = 1;
             
            // Find envelopes count for
            // each envelope
            for(int j = 0 ; j < i ; ++j)
            {
                 
                if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1] && dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                }
            }
             
            // Store maximum envelopes count
            max_envelope = Math.Max(max_envelope, dp[i]);
        }
         
        // Return the result
        return max_envelope;
    }
 
    // Driver code
    public static void Main(string[] args){
 
        // Given the envelopes
        int[][] envelopes = new int[][]{
            new int[]{ 4, 3 },
            new int[]{ 5, 3 },
            new int[]{ 5, 6 },
            new int[]{ 1, 2 }
        };
         
        // Function call
        Console.WriteLine(maxEnvelopes(envelopes));
         
    }
}
 
class comp : IComparer<int[]>{
    public int Compare(int[] a, int[] b)
    {
        if(a[0] != b[0]) return a[0] - b[0];
        return a[1] - b[1];
    }
}
 
// This code is contributed by entertain2022.

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function that returns the maximum
// number of envelopes that can be
// inserted into another envelopes
function maxEnvelopes(envelopes)
{
    // Number of envelopes
    var N = envelopes.length;
 
    if (N == 0)
        return N;
 
    // Sort the envelopes in
    // non-decreasing order
    envelopes.sort();
 
    // Initialize dp[] array
    var dp = Array(N);
 
    // To store the result
    var max_envelope = 1;
 
    dp[0] = 1;
 
    // Loop through the array
    for (var i = 1; i < N; ++i) {
        dp[i] = 1;
 
        // Find envelopes count for
        // each envelope
        for (var j = 0; j < i; ++j) {
 
            if (envelopes[i][0] > envelopes[j][0]
                && envelopes[i][1] > envelopes[j][1]
                && dp[i] < dp[j] + 1)
                dp[i] = dp[j] + 1;
        }
 
        // Store maximum envelopes count
        max_envelope = Math.max(max_envelope,
                        dp[i]);
    }
 
    // Return the result
    return max_envelope;
}
 
// Driver Code
 
// Given the envelopes
var envelopes
    = [ [ 4, 3 ], [ 5, 3 ], [ 5, 6 ], [ 1, 2 ] ];
     
// Function Call
document.write( maxEnvelopes(envelopes));
 
 
</script>
Producción: 

3

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)

Enfoque eficiente: para optimizar el enfoque ingenuo, la idea es utilizar el concepto de búsqueda binaria y la subsecuencia creciente más larga . Clasificar los sobres en orden creciente de ancho y en orden decreciente de altura si el ancho es el mismo, reduce el problema a encontrar la secuencia creciente más larga de altura del sobre. Este enfoque funciona ya que el ancho ya está clasificado en orden creciente y solo la secuencia máxima creciente de altura es suficiente para encontrar el número máximo de sobres. La forma eficiente de encontrar la secuencia creciente más larga en el enfoque N × log (N) se analiza en este artículo.

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 that returns the maximum
// number of envelopes that can be
// inserted into another envelopes
int maxEnvelopes(vector<vector<int> >& envelopes)
{
    // Number of envelopes
    int N = envelopes.size();
 
    if (N == 0)
        return N;
 
    // Sort the envelopes in increasing
    // order of width and decreasing order
    // of height is width is same
    sort(envelopes.begin(), envelopes.end(),
        [](vector<int>& a, vector<int>& b) {
            return a[0] < b[0]
                    or (a[0] == b[0] and a[1] > b[1]);
        });
 
    // To store the longest increasing
    // sequence of height
    vector<int> dp;
 
    // Finding LIS of the heights
    // of the envelopes
    for (int i = 0; i < N; ++i) {
        auto iter = lower_bound(dp.begin(),
                                dp.end(),
                                envelopes[i][1]);
 
        if (iter == dp.end())
            dp.push_back(envelopes[i][1]);
        else if (envelopes[i][1] < *iter)
            *iter = envelopes[i][1];
    }
 
    // Return the result
    return dp.size();
}
 
// Driver Code
int main()
{
    // Given the envelopes
    vector<vector<int> > envelopes
        = { { 4, 3 }, { 5, 3 }, { 5, 6 }, { 1, 2 } };
 
    // Function Call
    cout << maxEnvelopes(envelopes);
    return 0;
}
Producción: 

3

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

Publicación traducida automáticamente

Artículo escrito por d_hacked_scripter y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *