Compruebe si es posible reorganizar los rectángulos en un orden de ancho no ascendente

Posted on by Rudeus Greyrat

Dado un número n de rectángulos con su longitud L y su anchura B. Podemos girar cualquier rectángulo 90 grados. En otras palabras, después de darles la vuelta, el ancho se convertirá en largo y el largo en ancho. 
La tarea es verificar si hay una manera de hacer que los rectángulos vayan en orden de amplitud no ascendente. Es decir, el ancho de cada rectángulo no debe ser mayor que el ancho del rectángulo anterior. 
Nota: No puede cambiar el orden de los rectángulos.
Ejemplos: 
 

Entrada: 3 
l = 3, b = 4 
l1 = 4, b1 = 6 
l2 = 3, b2 = 5 
Salida: SÍ 
Los anchos dados son [ 4, 6, 5 ] podemos rotar el segundo y el tercer rectángulo para que el anchos satisfarán la condición anterior [4, 4, 3] (3 no es mayor que 4 y 4 no es mayor que 4), por lo que imprimimos SÍ. 
Entrada: 3 
1 60 
70 55 
56 80 
Salida: NO 
Los anchos son [ 60, 55, 80 ] como 55 55 o 56 > 55. Por lo tanto, no es posible organizar los anchos en orden no ascendente, por lo que lo haremos imprimir NO.

Enfoque: a continuación se muestra el algoritmo paso a paso para resolver este problema: 
 

  1. Inicialice n rectángulo con sus longitudes y anchuras.
  2. Iterar sobre el rectángulo de izquierda a derecha.
  3. Gire cada rectángulo de tal manera que su ancho sea lo más grande posible pero no mayor que el rectángulo anterior.
  4. Si en alguna iteración no existe tal forma de colocar el rectángulo, la respuesta es «NO»

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if it possible to form
// rectangles with heights as non-ascending
int rotateRec(int n, int L[], int B[])
{
 
    // set maximum
    int m = INT_MAX;
 
    for (int i = 0; i < n; i++) {
        // replace the maximum with previous maximum
        if (max(L[i], B[i]) <= m)
            m = max(L[i], B[i]);
 
        // replace the minimum with previous minimum
        else if (min(L[i], B[i]) <= m)
            m = min(L[i], B[i]);
 
        // print NO if the above
        // two conditions fail at least once
        else {
            return 0;
        }
    }
    return 1;
}
 
// Driver code
int main()
{
    // initialize the number of rectangles
    int n = 3;
 
    // initialize n rectangles with length and breadth
    int L[] = { 5, 5, 6 };
    int B[] = { 6, 7, 8 };
    rotateRec(n, L, B) == 1 ? cout << "YES"
                            : cout << "NO";
 
    return 0;
}

Java

// Java implementation of above approach
import java.io.*;
 
class GFG {
    
// Function to check if it possible to form
// rectangles with heights as non-ascending
 static int rotateRec(int n, int L[], int B[])
{
 
    // set maximum
    int m = Integer.MAX_VALUE;
 
    for (int i = 0; i < n; i++) {
        // replace the maximum with previous maximum
        if (Math.max(L[i], B[i]) <= m)
            m = Math.max(L[i], B[i]);
 
        // replace the minimum with previous minimum
        else if (Math.min(L[i], B[i]) <= m)
            m = Math.min(L[i], B[i]);
 
        // print NO if the above
        // two conditions fail at least once
        else {
            return 0;
        }
    }
    return 1;
}
 
// Driver code
 
    public static void main (String[] args) {
    // initialize the number of rectangles
    int n = 3;
 
    // initialize n rectangles with length and breadth
    int L[] = { 5, 5, 6 };
    int B[] = { 6, 7, 8 };
    if(rotateRec(n, L, B) == 1)
     System.out.println( "YES");
     else
     System.out.println( "NO");
    }
}
 // This Code is contributed by inder_verma..

Python3

# Python3 implementation of above approach
import sys;
 
# Function to check if it possible
# to form rectangles with heights
# as non-ascending
def rotateRec(n, L, B):
 
    # set maximum
    m = sys.maxsize;
 
    for i in range(n):
 
        # replace the maximum with
        # previous maximum
        if (max(L[i], B[i]) <= m):
            m = max(L[i], B[i]);
 
        # replace the minimum
        # with previous minimum
        elif (min(L[i], B[i]) <= m):
            m = min(L[i], B[i]);
 
        # print NO if the above two
        # conditions fail at least once
        else:
            return 0;
     
    return 1;
 
# Driver code
 
# initialize the number
# of rectangles
n = 3;
 
# initialize n rectangles
# with length and breadth
L = [5, 5, 6];
B = [ 6, 7, 8 ];
if(rotateRec(n, L, B) == 1):
    print("YES");
else:
    print("NO");
 
# This code is contributed by mits

C#

// C# implementation of above approach
using System;
 
class GFG
{
     
// Function to check if it possible
// to form rectangles with heights
// as non-ascending
static int rotateRec(int n, int []L,
                            int []B)
{
 
    // set maximum
    int m = int.MaxValue ;
 
    for (int i = 0; i < n; i++)
    {
        // replace the maximum with
        // previous maximum
        if (Math.Max(L[i], B[i]) <= m)
            m = Math.Max(L[i], B[i]);
 
        // replace the minimum with
        // previous minimum
        else if (Math.Min(L[i], B[i]) <= m)
            m = Math.Min(L[i], B[i]);
 
        // print NO if the above
        // two conditions fail
        // at least once
        else
        {
            return 0;
        }
    }
    return 1;
}
 
// Driver code
public static void Main ()
{
    // initialize the number
    // of rectangles
    int n = 3;
     
    // initialize n rectangles with
    // length and breadth
    int []L = { 5, 5, 6 };
    int []B = { 6, 7, 8 };
    if(rotateRec(n, L, B) == 1)
    Console.WriteLine("YES");
    else
    Console.WriteLine("NO");
}
}
 
// This code is contributed
// by inder_verma

PHP

<?php
// PHP implementation of above approach
 
// Function to check if it possible
// to form rectangles with heights
// as non-ascending
function rotateRec($n, $L, $B)
{
 
    // set maximum
    $m = PHP_INT_MAX;
 
    for ($i = 0; $i < $n; $i++)
    {
        // replace the maximum with
        // previous maximum
        if (max($L[$i], $B[$i]) <= $m)
            $m = max($L[$i], $B[$i]);
 
        // replace the minimum
        // with previous minimum
        else if (min($L[$i], $B[$i]) <= $m)
            $m = min($L[$i], $B[$i]);
 
        // print NO if the above two
        // conditions fail at least once
        else
        {
            return 0;
        }
    }
    return 1;
}
 
// Driver code
 
// initialize the number
// of rectangles
$n = 3;
 
// initialize n rectangles
// with length and breadth
$L = array(5, 5, 6 );
$B = array( 6, 7, 8 );
if(rotateRec($n, $L, $B) == 1)
    echo "YES";
else
    echo "NO";
 
// This code is contributed
// by Shashank
?>

Javascript

<script>
 
// javascript implementation of above approach
 
     
// Function to check if it possible
// to form rectangles with heights
// as non-ascending
function rotateRec( n, L, B)
{
 
    // set maximum
    var m = Number.MAX_VALUE
 
    for (var i = 0; i < n; i++)
    {
        // replace the maximum with
        // previous maximum
        if (Math.max(L[i], B[i]) <= m)
            m = Math.max(L[i], B[i]);
 
        // replace the minimum with
        // previous minimum
        else if (Math.min(L[i], B[i]) <= m)
            m = Math.min(L[i], B[i]);
 
        // print NO if the above
        // two conditions fail
        // at least once
        else
        {
            return 0;
        }
    }
    return 1;
}
 
// Driver code
 
    // initialize the number
    // of rectangles
    var n = 3;
     
    // initialize n rectangles with
    // length and breadth
    var L = [ 5, 5, 6 ];
    var B = [ 6, 7, 8 ];
    if(rotateRec(n, L, B) == 1)
    document.write("YES");
    else
    document.write("NO");
     
</script>
Producción: 

NO

 

Complejidad temporal: O(n)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por SrijaDe 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 *