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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public IList<IList<int>> GetSkyline(int[][] buildings) {
6 var events = new List<int[]>();
7 foreach (var b in buildings) {
8 events.Add(new int[] { b[0], -b[2] });
9 events.Add(new int[] { b[1], b[2] });
10 }
11 events.Sort((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
12
13 var res = new List<IList<int>>();
14 var heights = new SortedDictionary<int, int>();
15 heights[0] = 1;
16 int prev = 0;
17
18 foreach (var e in events) {
19 if (e[1] < 0) {
20 if (!heights.ContainsKey(-e[1])) heights[-e[1]] = 0;
21 heights[-e[1]]++;
22 } else {
23 heights[e[1]]--;
24 if (heights[e[1]] == 0) heights.Remove(e[1]);
25 }
26 int current = heights.Keys.Max();
27 if (current != prev) {
28 res.Add(new List<int>() { e[0], current });
29 prev = current;
30 }
31 }
32
33 return res;
34 }
35}This C# code uses a SortedDictionary to maintain active building heights. This serves as an ordered map similar to a multiset, allowing determination of the current skyline height efficiently and keeping track of changes in height as the algorithm processes through events sequentially.
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.