Проблема горизонта | Комплект 2

Опубликовано: 1 Января, 2022

Для n прямоугольных зданий в двухмерном городе вычисляет горизонт этих зданий, удаляя скрытые линии. Основная задача - осмотреть постройки со стороны и убрать все невидимые участки.
Все здания имеют общее основание, и каждое здание представлено тройкой (слева, справа, справа).

  • left: координата x на левой стороне (или стене).
  • right: координата x правой стороны.
  • ht: высота здания.

Линия горизонта - это набор прямоугольных полос. Прямоугольная полоса представлена в виде пары (left, ht), где left - координата x левой стороны полосы, а ht - высота полосы.

Примеры:

Input: 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: { {1, 11}, {3, 13}, {9, 0}, {12, 7}, {16, 3}, {19, 18}, {22, 3}, {23, 13}, {29, 0} }
Explanation:
The skyline is formed based on the key-points (representing by “green” dots) 
eliminating hidden walls of the buildings.
 

Input: buildings[ ][ ] = { {1, 11, 5} }
Output: { {1, 11}, {5, 0} }

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

  1. Из заданных троек для каждого здания найдите местоположение левой стены, высоту и значение местоположения правой стены.
  2. Сохраните левую стену с ее отрицательным значением высоты и правую стену с ее фактической высотой как пару в векторных стенах . Это сделано для того, чтобы различать левую и правую стены одного и того же здания.
  3. Отсортируйте стены в порядке возрастания.
  4. Пройдите через векторные стены , если левая стена найдена, сохраните высоту левой стены в мультимножестве M. В противном случае, если встречается правая стена, удалите ее соответствующую высоту из мультимножества .
  5. Проверьте, изменилось ли верхнее значение. Если оно изменилось, обновите верхнее значение и сохраните текущее значение абсциссы стены (x-cordinate) и обновленное верхнее значение в векторе в виде линии горизонта .
  6. Распечатайте пары значений, хранящиеся в векторе линии горизонта.

Ниже представлена реализация описанного выше подхода:

C ++

// C++ progrqam for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to create skyline
vector<pair< int , int > >
createSkyline(vector<vector< int > >& buildings)
{
// Get the number of buildings
int N = buildings.size();
// To store the left and right
// wall position of the buildings
vector<pair< int , int > > wall;
// Triplet of building structure
// parameters
int left, height, right;
for ( int i = 0; i < N; i++) {
// Get left point of building
left = buildings[i][0];
// Get height of building
height = buildings[i][1];
// Get right point of building
right = buildings[i][2];
// Store left point and height
// of the left wall
// Negative value means left wall
// will be inserted to multiset first
// for the same abscissa(x) as right wall
wall.push_back({ left, -height });
// Store right point and height
// of the right wall
wall.push_back(
make_pair(right, height));
}
// Sort the walls in ascending order
sort(wall.begin(), wall.end());
// To store skyline: output
vector<pair< int , int > > skyline;
// Initialize a multiset to
// keep left wall heights sorted
multiset< int > leftWallHeight = { 0 };
// Current max height among
// leftWallHeights
int top = 0;
// Traverse through the sorted walls
for ( auto w : wall) {
// If left wall is found
if (w.second < 0) {
// Insert the height
leftWallHeight.insert(-w.second);
}
// If right wall is found
else {
// Remove the height
leftWallHeight.erase(
leftWallHeight.find(w.second));
}
// Mark a skyline point if top changes
// .rbegin(): reverse iterator
if (*leftWallHeight.rbegin() != top) {
top = *leftWallHeight.rbegin();
skyline.push_back(
make_pair(w.first, top));
}
}
// Return skyline to printSkyline
return skyline;
}
// Function to print the output skyline
void printSkyline(
vector<vector< int > >& buildings)
{
// Function call for creating skyline
vector<pair< int , int > > skyline
= createSkyline(buildings);
cout << "Skyline for given"
<< " buildings: {" ;
for ( auto it : skyline) {
cout << "{" << it.first << ", "
<< it.second << "} " ;
}
cout << "}" ;
}
// Driver Code
int main()
{
vector<vector< int > > buildings;blockquote
// Given left and right location
// and height of the wall
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 } };
// Function Call
printSkyline(buildings);
return 0;
}
Выход:

Skyline for given buildings:
{{1, 11} {3, 13} {9, 0} {12, 7} {16, 3} {19, 18} {22, 3} {23, 13} {29, 0} }

Сложность времени: O (N * log (N))
Вспомогательное пространство: O (N)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.