Dadas dos arrays arr1[] y arr2[] de N que denotan N coordenadas de la forma (arr1[i], 0) y M enteros positivos que denotan M coordenadas de la forma (arr2[j], 1 ) donde 1 ≤ i ≤ N y 1≤ j ≤ METRO . La tarea es encontrar el área del rectángulo más grande que se puede formar usando estas coordenadas. Imprime 0 si no se puede formar un rectángulo.
Ejemplos:
Entrada: arr1[] = {1, 2, 4}, arr2[] = {1, 3, 4}
Salida: 3
Explicación: El rectángulo más grande posible es {(1, 0), (1, 1), (4 , 0), (4, 1)}.
Por lo tanto, área del rectángulo = largo * ancho = (4 – 1)*(1 – 0) = 3Entrada: arr1[] = {1, 3, 5}, arr2[] = {4, 2, 10}
Salida: 0
Explicación: No se puede formar ningún rectángulo. Por lo tanto, la respuesta es cero.
Enfoque ingenuo: el enfoque más simple es recorrer la array dada arr1[] y, para cada i , recorrer los puntos en arr2[] usando una variable j . Si arr1[i] es igual a arr2[j] , almacene el valor arr1[i] en una array separada, digamos ans[] . Después de encontrar todos esos valores, ordene la array ans[] e imprima el área máxima como ans[L] – ans[0] donde L es el índice del último elemento de ans[] ya que el ancho del rectángulo siempre será 1 .
Complejidad temporal: O(N*M)
Espacio auxiliar: O(M + N)
Enfoque eficiente: la idea es utilizar el algoritmo de clasificación y la técnica de dos puntos . Observa que el ancho del rectángulo siempre será 1 . Por lo tanto, el área máxima se puede encontrar maximizando su longitud. Siga los pasos a continuación para resolver el problema:
- Ordene las arrays dadas arr1[] y arr2[] .
- Inicialice las variables, comience y termine con 0 para almacenar el punto inicial y final de la longitud. Además, inicialice las variables i y j para recorrer la array arr1[] y arr2[] respectivamente.
- Si bien i es más pequeño que N y j más pequeño que M , verifique las siguientes condiciones:
- Si arr1[i] es lo mismo que arr2[j] y start es 0 , actualice start como start = arr1[i] . De lo contrario, actualice end como end = arr1[i] y luego incremente i y j en 1 .
- Si arr1[i] es mayor que arr2[j] , incremente j en 1 . De lo contrario, incremente i en 1 .
- Si inicio o final es 0 , imprima 0 . De lo contrario, imprima (fin – inicio) como el área máxima posible.
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 the maximum possible // area of a rectangle int largestArea(int arr1[], int n, int arr2[], int m) { // Initialize variables int end = 0, start = 0, i = 0, j = 0; // Sort array arr1[] sort(arr1, arr1 + n); // Sort array arr2[] sort(arr2, arr2 + m); // Traverse arr1[] and arr2[] while (i < n and j < m) { // If arr1[i] is same as arr2[j] if (arr1[i] == arr2[j]) { // If no starting point // is found yet if (start == 0) start = arr1[i]; else // Update maximum end end = arr1[i]; i++; j++; } // If arr[i] > arr2[j] else if (arr1[i] > arr2[j]) j++; else i++; } // If no rectangle is found if (end == 0 or start == 0) return 0; else // Return the area return (end - start); } // Driver Code int main() { // Given point int arr1[] = { 1, 2, 4 }; // Given length int N = sizeof(arr1) / sizeof(arr1[0]); // Given points int arr2[] = { 1, 3, 4 }; // Given length int M = sizeof(arr2) / sizeof(arr2[0]); // Function Call cout << largestArea(arr1, N, arr2, M); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the maximum possible // area of a rectangle static int largestArea(int arr1[], int n, int arr2[], int m) { // Initialize variables int end = 0, start = 0, i = 0, j = 0; // Sort array arr1[] Arrays.sort(arr1); // Sort array arr2[] Arrays.sort(arr1); // Traverse arr1[] and arr2[] while (i < n && j < m) { // If arr1[i] is same as arr2[j] if (arr1[i] == arr2[j]) { // If no starting point // is found yet if (start == 0) start = arr1[i]; else // Update maximum end end = arr1[i]; i++; j++; } // If arr[i] > arr2[j] else if (arr1[i] > arr2[j]) j++; else i++; } // If no rectangle is found if (end == 0 || start == 0) return 0; else // Return the area return (end - start); } // Driver Code public static void main(String args[]) { // Given point int arr1[] = { 1, 2, 4 }; // Given length int N = arr1.length; // Given points int arr2[] = { 1, 3, 4 }; // Given length int M = arr2.length; // Function Call System.out.println(largestArea(arr1, N, arr2, M)); } } // This code is contributed by bolliranadheer
Python3
# Python3 program for the above approach # Function to find the maximum possible # area of a rectangle def largestArea(arr1, n, arr2, m): # Initialize variables end = 0 start = 0 i = 0 j = 0 # Sort array arr1[] arr1.sort(reverse = False) # Sort array arr2[] arr2.sort(reverse = False) # Traverse arr1[] and arr2[] while (i < n and j < m): # If arr1[i] is same as arr2[j] if (arr1[i] == arr2[j]): # If no starting point # is found yet if (start == 0): start = arr1[i] else: # Update maximum end end = arr1[i] i += 1 j += 1 # If arr[i] > arr2[j] elif (arr1[i] > arr2[j]): j += 1 else: i += 1 # If no rectangle is found if (end == 0 or start == 0): return 0 else: # Return the area return (end - start) # Driver Code if __name__ == '__main__': # Given point arr1 = [ 1, 2, 4 ] # Given length N = len(arr1) # Given points arr2 = [ 1, 3, 4 ] # Given length M = len(arr2) # Function Call print(largestArea(arr1, N, arr2, M)) # This code is contributed by ipg2016107
C#
// C# program for the above approach using System; class GFG{ // Function to find the maximum possible // area of a rectangle static int largestArea(int[] arr1, int n, int[] arr2, int m) { // Initialize variables int end = 0, start = 0, i = 0, j = 0; // Sort array arr1[] Array.Sort(arr1); // Sort array arr2[] Array.Sort(arr2); // Traverse arr1[] and arr2[] while (i < n && j < m) { // If arr1[i] is same as arr2[j] if (arr1[i] == arr2[j]) { // If no starting point // is found yet if (start == 0) start = arr1[i]; else // Update maximum end end = arr1[i]; i++; j++; } // If arr[i] > arr2[j] else if (arr1[i] > arr2[j]) j++; else i++; } // If no rectangle is found if (end == 0 || start == 0) return 0; else // Return the area return (end - start); } // Driver code static void Main() { // Given point int[] arr1 = { 1, 2, 4 }; // Given length int N = arr1.Length; // Given points int[] arr2 = { 1, 3, 4 }; // Given length int M = arr2.Length; // Function Call Console.WriteLine(largestArea(arr1, N, arr2, M)); } } // This code is contributed by divyeshrabadiya07
Javascript
<script> // Javascript program for the above approach // Function to find the maximum possible // area of a rectangle function largestArea(arr1, n, arr2, m) { // Initialize variables var end = 0, start = 0, i = 0, j = 0; // Sort array arr1[] arr1.sort(); // Sort array arr2[] arr2.sort(); // Traverse arr1[] and arr2[] while (i < n && j < m) { // If arr1[i] is same as arr2[j] if (arr1[i] == arr2[j]) { // If no starting point // is found yet if (start == 0) start = arr1[i]; else // Update maximum end end = arr1[i]; i++; j++; } // If arr[i] > arr2[j] else if (arr1[i] > arr2[j]) j++; else i++; } // If no rectangle is found if (end == 0 || start == 0) return 0; else // Return the area return (end - start); } // Driver Code // Given point var arr1 = [ 1, 2, 4 ]; // Given length var N = arr1.length; // Given points var arr2 = [ 1, 3, 4 ]; // Given length var M = arr2.length; // Function Call document.write(largestArea(arr1, N, arr2, M)); // This code is contributed by noob2000. </script>
3
Complejidad de tiempo: O(N*log N + M*log M)
Espacio auxiliar: O(M+N)
Publicación traducida automáticamente
Artículo escrito por SaiNikhilKanchukatla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA