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.
1using System;
2using System.Collections.Generic;
public class Solution {
public IList<IList<int>> GetSkyline(int[][] buildings) {
return DivideAndConquer(buildings, 0, buildings.Length - 1);
}
private List<IList<int>> DivideAndConquer(int[][] buildings, int left, int right) {
if (left > right) return new List<IList<int>>();
if (left == right) return new List<IList<int>> { new List<int> { buildings[left][0], buildings[left][2] }, new List<int> { buildings[left][1], 0 } };
int mid = (left + right) / 2;
var leftSkyline = DivideAndConquer(buildings, left, mid);
var rightSkyline = DivideAndConquer(buildings, mid+1, right);
return Merge(leftSkyline, rightSkyline);
}
private List<IList<int>> Merge(List<IList<int>> left, List<IList<int>> right) {
var result = new List<IList<int>>();
int h1 = 0, h2 = 0, idx1 = 0, idx2 = 0;
while (idx1 < left.Count && idx2 < right.Count) {
int x, h;
if (left[idx1][0] < right[idx2][0]) {
x = left[idx1][0];
h1 = left[idx1][1];
idx1++;
} else if (right[idx2][0] < left[idx1][0]) {
x = right[idx2][0];
h2 = right[idx2][1];
idx2++;
} else {
x = left[idx1][0];
h1 = left[idx1][1];
h2 = right[idx2][1];
idx1++;
idx2++;
}
h = Math.Max(h1, h2);
if (result.Count == 0 || result[result.Count - 1][1] != h) {
result.Add(new List<int> { x, h });
}
}
AddRemaining(left, idx1, result);
AddRemaining(right, idx2, result);
return result;
}
private void AddRemaining(List<IList<int>> skyline, int idx, List<IList<int>> result) {
while (idx < skyline.Count) {
result.Add(skyline[idx++]);
}
}
}This C# solution exemplifies the divide and conquer paradigm, handling recursive skyline resolution by managing endpoints of buildings and maintaining height continuity for merged results.