Solution For The Skyline Problem
The Skyline Problem is a classic problem in computer science that deals with finding the outline of a 2D city skyline. Given a list of buildings represented as a 3-tuple (left edge, right edge, and height), the goal is to determine the height profile of the city skyline, represented as a list of (x-coordinate, height) points.
The input to the problem is a list of buildings, where each building is represented as a tuple (left_edge, right_edge, height). The output should be a list of coordinates that represent the skyline. Each coordinate is represented as a tuple (x_coordinate, height).
Approach:
We can solve this problem using the divide and conquer strategy. We will divide the input list of buildings into two halves and recursively find the skyline of each half. Then we will merge the two skylines to get the final result.
First find the middle index of the list and then divide it into two halves. This can be done using a simple binary search.
base case: If the list has only one building, return the skyline of that building, which is represented as two tuples (left_edge, height) and (right_edge, 0).
For the recursive case, we will merge the skylines of the left and right halves. The merge will be done by iterating over the two lists and keeping track of the last heights. The current heights will be determined by comparing the left height and right height. We will add the coordinate of the new point only if the height changes.
The algorithm will be implemented with the following steps:
If there is only one building in the list, return the coordinates of the left and right edges of the building with a height value.
Divide the list of buildings in two halves and recursively find the skylines of both halves.
Merge the two skylines to get the final result. This can be done by iterating over both skylines and updating the current heights for each building encountered. If the height changes, add the new point to the final result.
Return the final result.
Let’s consider a simple example to illustrate the algorithm:
Input: [(2,9,10), (3,6,6), (5,12,12), (15,20,8), (17,25,6)]
Output: [(2,10), (3,6), (6,12), (12,0), (15,8), (20,0), (25,6)]
We start by dividing the input list into two halves:
[(2,9,10), (3,6,6), (5,12,12)] and [(15,20,8), (17,25,6)]We recursively compute the skylines of both halves:
Left: [(2, 10), (9, 0), (3, 6), (6, 12), (5, 12), (12, 0)] Right: [(15, 8), (20, 0), (17, 6), (25, 6)]
We now merge the two skylines and get the final result:
[(2, 10), (3, 6), (6, 12), (12, 0), (15, 8), (20, 0), (25, 6)]This is the expected output.
Time Complexity:
The time complexity of this algorithm is O(n log n), where n is the number of buildings in the input list. This is because we divide the input list into halves at each recursive step and merge the two halves in linear time.
Space Complexity:
The space complexity of this algorithm is O(n log n), where n is the number of buildings in the input list. This is because we store the result in a list of size n log n due to the recursive calls.
Step by Step Implementation For The Skyline Problem
/**
* @author:
* @date:
* @description: Given an array of buildings, find the skyline of these buildings.
* The skyline is the set of points on the horizontal line where the height of the building is equal to or greater than its index.
* For example, the skyline of [3, 0, 8, 4, 5, 2, 6, 2, 2, 5, 2, 1, 3] is [(3, 10), (4, 5), (5, 2), (6, 2), (8, 0), (10, 1), (11, 3)].
*/
import java.util.*;
class Solution {
public List> getSkyline(int[][] buildings) {
List> result = new ArrayList>();
if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
return result;
}
// use TreeMap to store height and its count
// key: height, value: count
TreeMap heightMap = new TreeMap();
// add start point and end point height into the map
for (int[] building : buildings) {
// start point height
int startHeight = building[2];
// end point height
int endHeight = 0;
// add start point
if (!heightMap.containsKey(startHeight)) {
heightMap.put(startHeight, 1);
} else {
heightMap.put(startHeight, heightMap.get(startHeight) + 1);
}
// add end point
if (!heightMap.containsKey(endHeight)) {
heightMap.put(endHeight, 1);
} else {
heightMap.put(endHeight, heightMap.get(endHeight) + 1);
}
}
// use previous height to store current maximum height
int prevHeight = 0;
// iterate through the map to get the result
for (Map.Entry entry : heightMap.entrySet()) {
int currHeight = entry.getKey();
int count = entry.getValue();
// if current height is not equal to previous height, it means it is a critical point
if (prevHeight != currHeight) {
// add current height and its count into the result
result.add(new ArrayList(Arrays.asList(prevHeight, count)));
}
// update previous height
prevHeight = currHeight;
}
return result;
}
} def getSkyline(buildings):
# The idea is to process all buildings from left to right
# and for each building add its height to the "heights" list
# if it starts a new skyline, or update the height of the current
# skyline if it continues the current one.
# We also need to keep track of the "ends" of each skyline, so
# that we know when one skyline ends and a new one begins.
# Initialize empty lists to keep track of the current skyline
# and its corresponding "end"
skyline = []
ends = []
# Loop through all buildings
for b in buildings:
# If the current building starts a new skyline,
# add its height to the "heights" list
if not skyline or b[0] > ends[-1]:
skyline.append(b[2])
ends.append(b[1])
# If the current building continues the current skyline,
# update the height of the current skyline if necessary
elif b[2] > skyline[-1]:
skyline[-1] = b[2]
# If the current building ends the current skyline,
# remove the corresponding "end" from the "ends" list
elif b[1] == ends[-1]:
ends.pop()
skyline.pop()
# If there is a new skyline, add its height to the "heights" list
if skyline and b[2] > skyline[-1]:
skyline.append(b[2])
ends.append(b[1])
# Return the skyline
return skyline// The Skyline Problem
// A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).
// Buildings Skyline Contour
// The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
// For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
// The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
// For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
// Notes:
// The number of buildings in any input list is guaranteed to be in the range [0, 10000].
// The input list is already sorted in ascending order by the left x position Li.
// The output list must be sorted by the x position.
// There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]
// Credits:
// Special thanks to @stellari for adding this problem, creating these two awesome images and all test cases.
/**
* @param {number[][]} buildings
* @return {number[][]}
*/
var getSkyline = function(buildings) {
};There are multiple ways to solve the skyline problem. One approach is to use a max heap to keep track of the tallest buildings currently in view. As we iterate through the buildings, we add them to the heap if they are taller than the building at the top of the heap. If a building is shorter than the top of the heap, we remove the top of the heap and add the difference between the new top and the removed building to our skyline.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public IList> GetSkyline(int[][] buildings) {
// edge case
if (buildings.Length == 0) {
return new List>();
}
// create a list of critical points
List criticalPoints = new List();
foreach (int[] building in buildings) {
criticalPoints.Add(new CriticalPoint(building[0], building[2], true));
criticalPoints.Add(new CriticalPoint(building[1], building[2], false));
}
// sort critical points
criticalPoints.Sort();
// create a max heap to track tallest building
MaxHeap maxHeap = new MaxHeap();
// create a list of output
List> output = new List>();
// track previous height
int prevHeight = 0;
// iterate through critical points
foreach (CriticalPoint criticalPoint in criticalPoints) {
// if it's the start of a building, add it to the heap
if (criticalPoint.isStart) {
maxHeap.Add(criticalPoint.height);
} else {
// if it's the end of a building, remove it from the heap
maxHeap.Remove(criticalPoint.height);
}
// get the current tallest building
int currentTallest = maxHeap.GetMax();
// if the current tallest building is different from the previous one
if (currentTallest != prevHeight) {
// add it to the output
output.Add(new List() { criticalPoint.x, currentTallest });
// update prevHeight
prevHeight = currentTallest;
}
}
return output;
}
}
public class CriticalPoint : IComparable {
public int x;
public int height;
public bool isStart;
public CriticalPoint(int x, int height, bool isStart) {
this.x = x;
this.height = height;
this.isStart = isStart;
}
public int CompareTo(CriticalPoint other) {
if (this.x != other.x) {
return this.x.CompareTo(other.x);
} else {
return (this.isStart ? -this.height : this.height).CompareTo(other.isStart ? -other.height : other.height);
}
}
}
public class MaxHeap {
private List heap;
public MaxHeap() {
this.heap = new List();
}
public void Add(int val) {
this.heap.Add(val);
this.HeapifyUp(this.heap.Count - 1);
}
public void Remove(int val) {
int index = this.heap.IndexOf(val);
this.heap[index] = this.heap[this.heap.Count - 1];
this.heap.RemoveAt(this.heap.Count - 1);
if (this.heap.Count > 0 && index < this.heap.Count) {
this.HeapifyDown(index);
}
}
public int GetMax() {
if (this.heap.Count == 0) {
return 0;
}
return this.heap[0];
}
private void HeapifyUp(int index) {
while (index > 0 && this.heap[index] > this.heap[(index - 1) / 2]) {
int temp = this.heap[index];
this.heap[index] = this.heap[(index - 1) / 2];
this.heap[(index - 1) / 2] = temp;
index = (index - 1) / 2;
}
}
private void HeapifyDown(int index) {
while (index * 2 + 1 < this.heap.Count) {
int largestChildIndex = index * 2 + 1;
if (index * 2 + 2 < this.heap.Count && this.heap[index * 2 + 2] > this.heap[index * 2 + 1]) {
largestChildIndex = index * 2 + 2;
}
if (this.heap[index] < this.heap[largestChildIndex]) {
int temp = this.heap[index];
this.heap[index] = this.heap[largestChildIndex];
this.heap[largestChildIndex] = temp;
} else {
break;
}
index = largestChildIndex;
}
}
}