Skyline Problem In Java.
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 below. Write a program to output the skyline formed by these buildings collectively.
Lets simplify the problem statement and understand it correctly,
If there are many buildings in a area as shown in below picture, If same buildings is viewed from distance then what we can see is not all the buildings but the skyline that is borders of all buildings.
You can see skyline of buildings if viewed from a side and remove all sections that are not visible/overlapped.
All buildings have common base and every building is represented by 3 points(left, right, height)
‘left': is x coordinate of building left wall.
‘right': is x coordinate of building right wall
‘height': is height of building.
A skyline is a collection of rectangular strips. A rectangular strip is represented as a pair (left, height) where left is x coordinate of building left wall and height is height of building.
Lets understand what is the input and the expected output. INPUT: You are given a building coordinates as shown below,
int[][] skyscraper = { {2,9,10}, {3,6,15}, {5,12,12}, {13,16,10}, {15,17,5} };
OUTPUT: Skyline Coordinates = { {2,10}, {3,15}, {6,12}, {12,0}, {13,10}, {16,5}, {17,0} }
Algorithm
STEP 1:
In Step 1, we will break the problem from multiple buildings to 1 building.
Lets see what is required to draw skyline if we have only 1 building.
So what we will do in this step is break down multiple buildings recursively until only 1 building is left and identify diagonal coordinates of each building.
Breaking of building is done in same way as we break the array in merge sort.
public static void main(String[] args) {
int[][] skyscraper = {
{2,9,10},
{3,6,15},
{5,12,12},
{13,16,10},
{15,17,5}
};
List<int[]> listSkyline = getSkyline(0, skyscraper.length-1, skyscraper);
}
private static List<int[]> getSkyline(int low, int high, int[][] skyscraper) {
int mid = low + (high-low)/2;
List<int[]> skyLineDiagonalPoints = new ArrayList<int[]>();
if (low > high){
return skyLineDiagonalPoints;
}else if(low==high){
int[] point1 = new int[2];
point1[0] = skyscraper[low][0];
point1[1] = skyscraper[low][2];
int[] point2 = new int[2];
point2[0] = skyscraper[low][1];
point2[1] = 0;
skyLineDiagonalPoints.add(point1);
skyLineDiagonalPoints.add(point2);
return skyLineDiagonalPoints;
}else{
List<int[]> skyline1 = getSkyline(low, mid, skyscraper);
List<int[]> skyline2 = getSkyline(mid+1, high, skyscraper);
}
}
getSkyline() method above break multiple buildings into individual building and findout diagonal coordinates of each building. 
In first step buildings are broken down recursively until only 1 building is left,
We already know how to findout skyline for only 1 building. Just take diagonal coordinates of building.
As we broke down multiple buildings to single building, we will apply logic to solve single building that is why we will calculate diagonal coordinates of each individual building and return calculated diagonals to caller.
Once we return back, we will have diagonal coordiantes from 2 buildings at that point we need to start merging. We will see that later. lets calculate diagonal coordinate and return.
STEP 2:
In step 2, start merging coordinates of building by applying below rule.
1. From 2 coordinates (x0, y0) of Building 0 and (x1, y1) of Building 1, compare x0 and x1,
whichever is smaller among them that is whichever building appeared first among them will be
part of output.
Say x0 is smaller, So x0 from Building 0 will be part of output. What about the height coordinate?
For height coordinate, it can't simply pick y0 because y0 can be overlapped by some taller
building, so for height coordinate it has to compare y0 of current Building 0 with previously
encountered height from Building 1 and whichever is greater that will be height coordinate.
Say height from Building 0 is greater so y0 will be height coordinate
So output coordinate will be (x0, y0).
Lets take one example and try to understand it.
Corner Case:
There are some corner cases like if 2 building start from same coordinate, so what to do in that case,
Consider like example below,
Java Program for Skyline problem.
package javabypatel;
import java.util.ArrayList;
import java.util.List;
public class SkylineProblemSolution {
public static void main(String[] args) {
int[][] skyscraper = {
{2,9,10},
{3,6,15},
{5,12,12},
{13,16,10},
{15,17,5}
};
List<int[]> listSkyline = getSkyline(0, skyscraper.length-1, skyscraper);
for (int[] is : listSkyline) {
System.out.println(is[0] + "," + is[1]);
}
System.out.println(listSkyline);
}
private static List<int[]> getSkyline(int low, int high, int[][] skyscraper) {
int mid = low + (high-low)/2;
List<int[]> skyLineDiagonalPoints = new ArrayList<int[]>();
if (low > high){
return skyLineDiagonalPoints;
}else if(low==high){
int[] point1 = new int[2];
point1[0] = skyscraper[low][0];
point1[1] = skyscraper[low][2];
int[] point2 = new int[2];
point2[0] = skyscraper[low][1];
point2[1] = 0;
skyLineDiagonalPoints.add(point1);
skyLineDiagonalPoints.add(point2);
return skyLineDiagonalPoints;
}else{
List<int[]> skyline1 = getSkyline(low, mid, skyscraper);
List<int[]> skyline2 = getSkyline(mid+1, high, skyscraper);
return mergeSkyLines(skyline1, skyline2);
}
}
private static List<int[]> mergeSkyLines(List<int[]> skyline1, List<int[]> skyline2) {
List<int[]> mergedSkyLineDiagonalPoints = new ArrayList<int[]>();
int lastHeightSkyScraper1 = 0;
int lastHeightSkyScraper2 = 0;
while( !(skyline1.isEmpty() || skyline2.isEmpty()) ){
if(skyline1.get(0)[0] < skyline2.get(0)[0]){
int maxHeight = skyline1.get(0)[1];
if(skyline1.get(0)[1] < lastHeightSkyScraper2){
maxHeight = lastHeightSkyScraper2;
}
lastHeightSkyScraper1 = skyline1.get(0)[1];
mergedSkyLineDiagonalPoints.add(new int[]{skyline1.get(0)[0], maxHeight});
skyline1.remove(0);
}else if(skyline1.get(0)[0] > skyline2.get(0)[0]){
int maxHeight = skyline2.get(0)[1];
if(skyline2.get(0)[1] < lastHeightSkyScraper1){
maxHeight = lastHeightSkyScraper1;
}
lastHeightSkyScraper2 = skyline2.get(0)[1];
mergedSkyLineDiagonalPoints.add(new int[]{skyline2.get(0)[0], maxHeight});
skyline2.remove(0);
}else{
int maxHeight = skyline1.get(0)[1] > skyline2.get(0)[1] ? skyline1.get(0)[1] : skyline2.get(0)[1];
mergedSkyLineDiagonalPoints.add( new int[]{skyline1.get(0)[0], maxHeight} );
lastHeightSkyScraper1 = skyline1.get(0)[1];
lastHeightSkyScraper2 = skyline2.get(0)[1];
skyline1.remove(0);
skyline2.remove(0);
}
}
while(!skyline1.isEmpty()){
mergedSkyLineDiagonalPoints.add( new int[]{skyline1.get(0)[0], skyline1.get(0)[1]} );
skyline1.remove(0);
}
while(!skyline2.isEmpty()){
mergedSkyLineDiagonalPoints.add( new int[]{skyline2.get(0)[0], skyline2.get(0)[1]} );
skyline2.remove(0);
}
//Remove Points falling at same height
for (int i = 0; i < mergedSkyLineDiagonalPoints.size(); i++) {
int j = i+1;
while(j < mergedSkyLineDiagonalPoints.size() && mergedSkyLineDiagonalPoints.get(j)[1] == mergedSkyLineDiagonalPoints.get(i)[1]){
mergedSkyLineDiagonalPoints.remove(j);
j++;
}
}
return mergedSkyLineDiagonalPoints;
}
}
You may also like to see
0/1 Knapsack Problem solved using Iterative and Dynamic Programming
Stock Buy Sell to Maximize Profit.
Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted
Count trailing zeros in factorial of a number.
How to Detect loop in linked list.
Tower Of Hanoi Program in Java.
Print Matrix Diagonally OR Diagonal order of Matrix.
Rotate Matrix by 90 degrees clockwise Inplace
Implement Queue using One Stack in Java (Recursive Implementation)
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment