Dados n edificios rectangulares en una ciudad bidimensional, calcula el horizonte de estos edificios, eliminando las líneas ocultas. La tarea principal es ver los edificios desde un lado y eliminar todas las secciones que no son visibles.
Todos los edificios comparten un fondo común y cada edificio está representado por un triplete (izquierda, altura, derecha)
- ‘izquierda’: es la coordenada x del lado izquierdo (o pared).
- ‘derecha’: es la coordenada x del lado derecho
- ‘ht’: es la altura del edificio.
Un horizonte es una colección de franjas rectangulares. Una franja rectangular se representa como un par (izquierda, altura) donde izquierda es la coordenada x del lado izquierdo de la franja y ht es la altura de la franja.
Ejemplos:
Input: Array of buildings
{ (1, 11, 5), (2, 6, 7), (3, 13, 9), (12, 7, 16), (14, 3, 25),
(19, 18, 22), (23, 13, 29), (24, 4, 28) }
Output: Skyline (an array of rectangular strips)
A strip has x coordinate of left side and height
(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18),
(22, 3), (25, 0)
Below image is for input 1 :
Consider following as another example when there is only one
building
Input: {(1, 11, 5)}
Output: (1, 11), (5, 0)
Una solución simple es inicializar el horizonte o el resultado como vacío, luego, uno por uno, agregar edificios al horizonte. Se agrega un edificio encontrando primero las tiras superpuestas. Si no hay franjas superpuestas, el nuevo edificio agrega nuevas franjas. Si se encuentra una tira superpuesta, la altura de la tira existente puede aumentar. La complejidad temporal de esta solución es O(n 2 )
Podemos encontrar Skyline en tiempo Θ(nLogn) usando Divide and Conquer . La idea es similar a Merge Sort , dividir el conjunto dado de edificios en dos subconjuntos. Construya recursivamente el horizonte en dos mitades y finalmente fusione los dos horizontes.
¿Cómo fusionar dos Skylines?
La idea es similar a la fusión del tipo de fusión, comience desde las primeras tiras de dos horizontes, compare las coordenadas x. Elija la tira con la coordenada x más pequeña y agréguela al resultado. La altura de la franja añadida se considera como el máximo de las alturas actuales de skyline1 y skyline2.
Ejemplo para mostrar el funcionamiento de la combinación:
Height of new Strip is always obtained by takin maximum of following
(a) Current height from skyline1, say 'h1'.
(b) Current height from skyline2, say 'h2'
h1 and h2 are initialized as 0. h1 is updated when a strip from
SkyLine1 is added to result and h2 is updated when a strip from
SkyLine2 is added.
Skyline1 = {(1, 11), (3, 13), (9, 0), (12, 7), (16, 0)}
Skyline2 = {(14, 3), (19, 18), (22, 3), (23, 13), (29, 0)}
Result = {}
h1 = 0, h2 = 0
Compare (1, 11) and (14, 3). Since first strip has smaller left x,
add it to result and increment index for Skyline1.
h1 = 11, New Height = max(11, 0)
Result = {(1, 11)}
Compare (3, 13) and (14, 3). Since first strip has smaller left x,
add it to result and increment index for Skyline1
h1 = 13, New Height = max(13, 0)
Result = {(1, 11), (3, 13)}
Similarly (9, 0) and (12, 7) are added.
h1 = 7, New Height = max(7, 0) = 7
Result = {(1, 11), (3, 13), (9, 0), (12, 7)}
Compare (16, 0) and (14, 3). Since second strip has smaller left x,
it is added to result.
h2 = 3, New Height = max(7, 3) = 7
Result = {(1, 11), (3, 13), (9, 0), (12, 7), (14, 7)}
Compare (16, 0) and (19, 18). Since first strip has smaller left x,
it is added to result.
h1 = 0, New Height = max(0, 3) = 3
Result = {(1, 11), (3, 13), (9, 0), (12, 7), (14, 7), (16, 3)}
Since Skyline1 has no more items, all remaining items of Skyline2
are added
Result = {(1, 11), (3, 13), (9, 0), (12, 7), (14, 7), (16, 3),
(19, 18), (22, 3), (23, 13), (29, 0)}
One observation about above output is, the strip (14, 7) is redundant
(There is already an strip of same height). We remove all redundant
strips.
Result = {(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18),
(22, 3), (23, 13), (29, 0)}
In below code, redundancy is handled by not appending a strip if the
previous strip in result has same height.
A continuación se muestra la implementación en C++ de la idea anterior.
// A divide and conquer based C++
// program to find skyline of given buildings
#include <iostream>
using namespace std;
// A structure for building
struct Building {
// x coordinate of left side
int left;
// height
int ht;
// x coordinate of right side
int right;
};
// A strip in skyline
class Strip {
// x coordinate of left side
int left;
// height
int ht;
public:
Strip(int l = 0, int h = 0)
{
left = l;
ht = h;
}
friend class SkyLine;
};
// Skyline: To represent Output(An array of strips)
class SkyLine {
// Array of strips
Strip* arr;
// Capacity of strip array
int capacity;
// Actual number of strips in array
int n;
public:
~SkyLine() { delete[] arr; }
int count() { return n; }
// A function to merge another skyline
// to this skyline
SkyLine* Merge(SkyLine* other);
// Constructor
SkyLine(int cap)
{
capacity = cap;
arr = new Strip[cap];
n = 0;
}
// Function to add a strip 'st' to array
void append(Strip* st)
{
// Check for redundant strip, a strip is
// redundant if it has same height or left as previous
if (n > 0 && arr[n - 1].ht == st->ht)
return;
if (n > 0 && arr[n - 1].left == st->left) {
arr[n - 1].ht = max(arr[n - 1].ht, st->ht);
return;
}
arr[n] = *st;
n++;
}
// A utility function to print all strips of
// skyline
void print()
{
for (int i = 0; i < n; i++) {
cout << " (" << arr[i].left << ", "
<< arr[i].ht << "), ";
}
}
};
// This function returns skyline for a
// given array of buildings arr[l..h].
// This function is similar to mergeSort().
SkyLine* findSkyline(Building arr[], int l, int h)
{
if (l == h) {
SkyLine* res = new SkyLine(2);
res->append(
new Strip(
arr[l].left, arr[l].ht));
res->append(
new Strip(
arr[l].right, 0));
return res;
}
int mid = (l + h) / 2;
// Recur for left and right halves
// and merge the two results
SkyLine* sl = findSkyline(
arr, l, mid);
SkyLine* sr = findSkyline(
arr, mid + 1, h);
SkyLine* res = sl->Merge(sr);
// To avoid memory leak
delete sl;
delete sr;
// Return merged skyline
return res;
}
// Similar to merge() in MergeSort
// This function merges another skyline
// 'other' to the skyline for which it is called.
// The function returns pointer to the
// resultant skyline
SkyLine* SkyLine::Merge(SkyLine* other)
{
// Create a resultant skyline with
// capacity as sum of two skylines
SkyLine* res = new SkyLine(
this->n + other->n);
// To store current heights of two skylines
int h1 = 0, h2 = 0;
// Indexes of strips in two skylines
int i = 0, j = 0;
while (i < this->n && j < other->n) {
// Compare x coordinates of left sides of two
// skylines and put the smaller one in result
if (this->arr[i].left < other->arr[j].left) {
int x1 = this->arr[i].left;
h1 = this->arr[i].ht;
// Choose height as max of two heights
int maxh = max(h1, h2);
res->append(new Strip(x1, maxh));
i++;
}
else {
int x2 = other->arr[j].left;
h2 = other->arr[j].ht;
int maxh = max(h1, h2);
res->append(new Strip(x2, maxh));
j++;
}
}
// If there are strips left in this
// skyline or other skyline
while (i < this->n) {
res->append(&arr[i]);
i++;
}
while (j < other->n) {
res->append(&other->arr[j]);
j++;
}
return res;
}
// Driver Function
int main()
{
Building arr[] = {
{ 1, 11, 5 }, { 2, 6, 7 }, { 3, 13, 9 }, { 12, 7, 16 }, { 14, 3, 25 }, { 19, 18, 22 }, { 23, 13, 29 }, { 24, 4, 28 }
};
int n = sizeof(arr) / sizeof(arr[0]);
// Find skyline for given buildings
// and print the skyline
SkyLine* ptr = findSkyline(arr, 0, n - 1);
cout << " Skyline for given buildings is \n";
ptr->print();
return 0;
}
Producción:
Skyline for given buildings is (1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (23, 13), (29, 0),
La complejidad de tiempo de la implementación recursiva anterior es la misma que Merge Sort.
T(n) = T(n/2) + Θ(n)
La solución de la recurrencia anterior es Θ(nLogn)
Referencias:
- http://faculty.kfupm.edu.sa/ics/darwish/stuff/ics353handouts/Ch4Ch5.pdf
- www.cs.ucf.edu/~sarahb/COP3503/Lectures/DivideAndConquer.ppt
Este artículo es aportado por Abhay Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA