Проблема горизонта | Комплект 2
Для 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}, прежде чем переходить к решению.
Подход:
- Из заданных троек для каждого здания найдите местоположение левой стены, высоту и значение местоположения правой стены.
- Сохраните левую стену с ее отрицательным значением высоты и правую стену с ее фактической высотой как пару в векторных стенах . Это сделано для того, чтобы различать левую и правую стены одного и того же здания.
- Отсортируйте стены в порядке возрастания.
- Пройдите через векторные стены , если левая стена найдена, сохраните высоту левой стены в мультимножестве M. В противном случае, если встречается правая стена, удалите ее соответствующую высоту из мультимножества .
- Проверьте, изменилось ли верхнее значение. Если оно изменилось, обновите верхнее значение и сохраните текущее значение абсциссы стены (x-cordinate) и обновленное верхнее значение в векторе в виде линии горизонта .
- Распечатайте пары значений, хранящиеся в векторе линии горизонта.
Ниже представлена реализация описанного выше подхода:
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.