Dados cuatro arreglos x1[] , x2[] , y1[] , y2[] de tamaño N donde ( x1[i] , y1[i] ) denota la esquina inferior izquierda y ( x2[i] , y2[i] ) esquina superior derecha de un rectángulo, la tarea es encontrar el número máximo de rectángulos superpuestos con al menos un punto común.
Ejemplos:
Entrada: N = 2 x1[] = {0, 50} y1[] = {0, 50} x2[] = {100, 60} y2[] = {100, 60}
Salida: 2
Explicación: Hay dos rectángulos {{0, 0}, {100, 100}}, {{50, 50}, {60, 60}} y ambos se cruzan como se muestra en la siguiente figura:
Entrada: N = 2 x1[] = {0, 100} y1[] = {0, 100} x2[] = {100, 200} y2[] = {100, 200}
Salida: 1
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso, que se basa en la idea de que cada rectángulo en el plano de coordenadas tiene su propia región y cuando se agregan varios rectángulos en el mismo plano, crean intersecciones entre sí. Por lo tanto, para seleccionar el número máximo de rectángulos superpuestos en el área común, elija con avidez el área de 1×1 unidad ya que todas las áreas superpuestas tendrán al menos esta cantidad de bloques. Siga los pasos a continuación para resolver el problema dado:
- Dado que hay N rectángulos y cada rectángulo tiene 2 coordenadas X y 2 coordenadas Y. Habrá un total de 2*N número de coordenadas X y coordenadas Y.
- Por lo tanto, cree un vector de coordenadas X e Y y empuje todas las X e Y de los rectángulos en los respectivos vectores.
- Inicialice una variable, digamos maxRectangles como 0 que almacena el máximo de rectángulos superpuestos.
- Recorra el vector X[] y para cada coordenada X[i] , recorra el vector Y[] y encuentre el número de rectángulos superpuestos con X[i] y después de este paso, actualice el valor de maxRectangles a un máximo de maxRectangles y cuente obtenido para la iteración actual.
- Después de completar los pasos anteriores, imprima el valor de maxRectangles como resultado.
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 number
// of overlapping rectangles
void maxOverlappingRectangles(
int x1[], int y1[], int x2[],
int y2[], int N)
{
// Stores the maximum count of
// overlapping rectangles
int max_rectangles = 0;
// Stores the X and Y coordinates
vector<int> X, Y;
for (int i = 0; i < N; i++) {
X.push_back(x1[i]);
X.push_back(x2[i] - 1);
Y.push_back(y1[i]);
Y.push_back(y2[i] - 1);
}
// Iterate over all pairs of Xs and Ys
for (int i = 0; i < X.size(); i++) {
for (int j = 0; j < Y.size(); j++) {
// Store the count for the
// current X and Y
int cnt = 0;
for (int k = 0; k < N; k++) {
if (X[i] >= x1[k]
&& X[i] + 1 <= x2[k]
&& Y[j] >= y1[k]
&& Y[j] + 1 <= y2[k]) {
cnt++;
}
}
// Update the maximum count of
// rectangles
max_rectangles = max(
max_rectangles, cnt);
}
}
// Returns the total count
cout << max_rectangles;
}
// Driver Code
int main()
{
int x1[] = { 0, 50 };
int y1[] = { 0, 50 };
int x2[] = { 100, 60 };
int y2[] = { 100, 60 };
int N = sizeof(x1) / sizeof(x1[0]);
maxOverlappingRectangles(
x1, y1, x2, y2, N);
return 0;
}
Java
// java program for the above approach
import java.util.*;
class GFG
{
// Function to find the maximum number
// of overlapping rectangles
static void maxOverlappingRectangles(int[] x1, int[] y1,
int[] x2, int[] y2,
int N)
{
// Stores the maximum count of
// overlapping rectangles
int max_rectangles = 0;
// Stores the X and Y coordinates
Vector<Integer> X = new Vector<>();
Vector<Integer> Y = new Vector<>();
for (int i = 0; i < N; i++) {
X.add(x1[i]);
X.add(x2[i] - 1);
Y.add(y1[i]);
Y.add(y2[i] - 1);
}
// Iterate over all pairs of Xs and Ys
for (int i = 0; i < X.size(); i++) {
for (int j = 0; j < Y.size(); j++) {
// Store the count for the
// current X and Y
int cnt = 0;
for (int k = 0; k < N; k++) {
if (X.get(i)>= x1[k] && X.get(i) + 1 <= x2[k]
&& Y.get(j) >= y1[k]
&& Y.get(j) + 1 <= y2[k]) {
cnt++;
}
}
// Update the maximum count of
// rectangles
max_rectangles
= Math.max(max_rectangles, cnt);
}
}
// Returns the total count
System.out.println(max_rectangles);
}
// Driver Code
public static void main(String[] args)
{
int[] x1 = { 0, 50 };
int[] y1 = { 0, 50 };
int[] x2 = { 100, 60 };
int[] y2 = { 100, 60 };
int N = x1.length;
maxOverlappingRectangles(x1, y1, x2, y2, N);
}
}
// This code is contributed by amreshkumar3.
Python3
# Python3 program for the above approach # Function to find the maximum number # of overlapping rectangles def maxOverlappingRectangles(x1, y1, x2, y2, N): # Stores the maximum count of # overlapping rectangles max_rectangles = 0 # Stores the X and Y coordinates X = [] Y = [] for i in range(0, N): X.append(x1[i]) X.append(x2[i] - 1) Y.append(y1[i]) Y.append(y2[i] - 1) # Iterate over all pairs of Xs and Ys for i in range(0, len(X)): for j in range(0, len(Y)): # Store the count for the # current X and Y cnt = 0 for k in range(0, N): if (X[i] >= x1[k] and X[i] + 1 <= x2[k] and Y[j] >= y1[k] and Y[j] + 1 <= y2[k]): cnt += 1 # Update the maximum count of # rectangles max_rectangles = max(max_rectangles, cnt) # Returns the total count print(max_rectangles) # Driver Code if __name__ == "__main__": x1 = [0, 50] y1 = [0, 50] x2 = [100, 60] y2 = [100, 60] N = len(x1) maxOverlappingRectangles(x1, y1, x2, y2, N) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the maximum number
// of overlapping rectangles
static void maxOverlappingRectangles(int[] x1, int[] y1,
int[] x2, int[] y2,
int N)
{
// Stores the maximum count of
// overlapping rectangles
int max_rectangles = 0;
// Stores the X and Y coordinates
List<int> X = new List<int>();
List<int> Y = new List<int>();
for (int i = 0; i < N; i++) {
X.Add(x1[i]);
X.Add(x2[i] - 1);
Y.Add(y1[i]);
Y.Add(y2[i] - 1);
}
// Iterate over all pairs of Xs and Ys
for (int i = 0; i < X.Count; i++) {
for (int j = 0; j < Y.Count; j++) {
// Store the count for the
// current X and Y
int cnt = 0;
for (int k = 0; k < N; k++) {
if (X[i] >= x1[k] && X[i] + 1 <= x2[k]
&& Y[j] >= y1[k]
&& Y[j] + 1 <= y2[k]) {
cnt++;
}
}
// Update the maximum count of
// rectangles
max_rectangles
= Math.Max(max_rectangles, cnt);
}
}
// Returns the total count
Console.WriteLine(max_rectangles);
}
// Driver Code
public static void Main()
{
int[] x1 = { 0, 50 };
int[] y1 = { 0, 50 };
int[] x2 = { 100, 60 };
int[] y2 = { 100, 60 };
int N = x1.Length;
maxOverlappingRectangles(x1, y1, x2, y2, N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the maximum number
// of overlapping rectangles
function maxOverlappingRectangles(
x1, y1, x2,
y2, N)
{
// Stores the maximum count of
// overlapping rectangles
let max_rectangles = 0;
// Stores the X and Y coordinates
let X = [], Y = [];
for (let i = 0; i < N; i++) {
X.push(x1[i]);
X.push(x2[i] - 1);
Y.push(y1[i]);
Y.push(y2[i] - 1);
}
// Iterate over all pairs of Xs and Ys
for (let i = 0; i < X.length; i++) {
for (let j = 0; j < Y.length; j++) {
// Store the count for the
// current X and Y
let cnt = 0;
for (let k = 0; k < N; k++) {
if (X[i] >= x1[k]
&& X[i] + 1 <= x2[k]
&& Y[j] >= y1[k]
&& Y[j] + 1 <= y2[k]) {
cnt++;
}
}
// Update the maximum count of
// rectangles
max_rectangles = Math.max(
max_rectangles, cnt);
}
}
// Returns the total count
document.write(max_rectangles);
}
// Driver Code
let x1 = [0, 50];
let y1 = [0, 50];
let x2 = [100, 60];
let y2 = [100, 60];
let N = x1.length;
maxOverlappingRectangles(
x1, y1, x2, y2, N);
// This code is contributed by Potta Lokesh
</script>
Producción:
2
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA