Sponsored
Sponsored
The Sweep Line algorithm involves moving a vertical line from left to right over the x-coordinates and maintaining a list of currently active buildings using a max-heap. The priority queue helps keep track of the tallest building at each point. As the line reaches the start of a new building, add it to the heap, and as it reaches the end of a building, remove it. The key points are detected based on changes in the maximum height at points where buildings start or end.
Time Complexity: O(N log N), where N is the number of events (two for each building).
Space Complexity: O(N), as we store up to N building heights in the heap.
1function getSkyline(buildings) {
2 const events = [];
3 for (const [left, right, height] of buildings) {
4 events.push([left, -height]);
5 events.push([right, height]);
6 }
7 events.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));
8
9 const result = [];
10 const heights = new Map();
11 heights.set(0, 1);
12 let prevMaxHeight = 0;
13
14 for (const [x, h] of events) {
15 if (h < 0) {
16 heights.set(-h, (heights.get(-h) || 0) + 1);
17 } else {
18 heights.set(h, heights.get(h) - 1);
19 if (heights.get(h) === 0) {
20 heights.delete(h);
21 }
22 }
23 const currentMaxHeight = Math.max(...heights.keys());
24 if (currentMaxHeight !== prevMaxHeight) {
25 result.push([x, currentMaxHeight]);
26 prevMaxHeight = currentMaxHeight;
27 }
28 }
29 return result;
30}This JavaScript solution utilizes a map to simulate the behavior of a priority queue by maintaining active building heights, ensuring that each point effectively and efficiently shows the highest height change. It results in optimized key point output by directly managing increase or decrease of building impacts through event processing.
This approach involves breaking down the problem using the divide and conquer strategy. The buildings array is split into two halves recursively. The base case is a single building, where the skyline can directly be calculated. The results are then merged, taking care of overlapping heights and ensuring continuity and distinct key points.
Time Complexity: O(N log N), due to division of buildings and merging.
Space Complexity: O(N), needing space for recursive stack and individual skyline lists.
1#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> mergeSkyline(const vector<vector<int>>& left, const vector<vector<int>>& right) {
int i = 0, j = 0, h1 = 0, h2 = 0;
vector<vector<int>> res;
while (i < left.size() && j < right.size()) {
int x, maxHeight;
if (left[i][0] < right[j][0]) {
x = left[i][0];
h1 = left[i][1];
++i;
} else if (left[i][0] > right[j][0]) {
x = right[j][0];
h2 = right[j][1];
++j;
} else {
x = left[i][0];
h1 = left[i][1];
h2 = right[j][1];
++i; ++j;
}
maxHeight = max(h1, h2);
if (res.empty() || res.back()[1] != maxHeight) {
res.push_back({x, maxHeight});
}
}
while (i < left.size()) {
res.push_back(left[i++]);
}
while (j < right.size()) {
res.push_back(right[j++]);
}
return res;
}
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
if (buildings.empty()) return {};
if (buildings.size() == 1) {
return { {buildings[0][0], buildings[0][2]}, {buildings[0][1], 0} };
}
int mid = buildings.size() / 2;
vector<vector<int>> left(buildings.begin(), buildings.begin() + mid);
vector<vector<int>> right(buildings.begin() + mid, buildings.end());
return mergeSkyline(getSkyline(left), getSkyline(right));
}This C++ code implements a divide and conquer algorithm with careful management of recursive splits and merging routines to ensure the skyline is constructed efficiently while minimizing redundant operations via height and position checks.