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.
1#include <vector>
2#include <set>
3#include <algorithm>
4using namespace std;
5
6vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
7 vector<pair<int, int>> events;
8 for (auto& b : buildings) {
9 events.emplace_back(b[0], -b[2]);
10 events.emplace_back(b[1], b[2]);
11 }
12 sort(events.begin(), events.end());
13
14 multiset<int> heights = {0};
15 vector<vector<int>> res;
16 int prev = 0;
17
18 for (const auto& e : events) {
19 if (e.second < 0) {
20 heights.insert(-e.second);
21 } else {
22 heights.erase(heights.find(e.second));
23 }
24 int current = *heights.rbegin();
25 if (current != prev) {
26 res.push_back({e.first, current});
27 prev = current;
28 }
29 }
30
31 return res;
32}This C++ solution employs a multiset to track the heights of buildings, similar to using a priority queue. By managing events and ensuring at each point the skyline height reflects the maximum possible height, the code outputs the required key points only when there's a change.
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.
1function
The JavaScript solution applies a divide and conquer algorithm to split the problem space into manageable segments, solving for each individually, and consolidating results with aligned key height changes.