Skyline Problem Algorithm
The Skyline Problem Algorithm is an efficient computational approach designed to solve the Skyline Problem, which involves determining the points that form the skyline of a given set of buildings in a 2-dimensional city landscape. The problem can be visualized by imagining a city where buildings are represented by rectangles with varying widths and heights, and the skyline is the outer contour created by merging these rectangles. The algorithm aims to find a sequence of key points that denote the changes in the heights of the contiguous buildings from left to right, thus representing the skyline.
There are several algorithms available to address the Skyline Problem, including the Divide and Conquer Algorithm, the Sweep Line Algorithm, and the Priority Queue based Algorithm. The Divide and Conquer Algorithm is a popular approach, which works by dividing the given set of buildings into two halves and recursively solving the problem for each half. After obtaining the skylines for both halves, the algorithm then merges these two skylines to form the final skyline. The overall time complexity of this approach is O(n log n), where n is the number of buildings. This algorithm is efficient and scalable, making it a widely-used solution for the Skyline Problem.
package Others;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
public class SkylineProblem {
Building[] building;
int count;
public void run() {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
this.building = new Building[num];
for (int i = 0; i < num; i++) {
String input = sc.next();
String[] data = input.split(",");
this.add(Integer.parseInt(data[0]), Integer.parseInt(data[1]), Integer.parseInt(data[2]));
}
this.print(this.findSkyline(0, num - 1));
sc.close();
}
public void add(int left, int height, int right) {
building[count++] = new Building(left, height, right);
}
public void print(ArrayList<Skyline> skyline) {
Iterator<Skyline> it = skyline.iterator();
while (it.hasNext()) {
Skyline temp = it.next();
System.out.print(temp.coordinates + "," + temp.height);
if (it.hasNext()) {
System.out.print(",");
}
}
}
public ArrayList<Skyline> findSkyline(int start, int end) {
if (start == end) {
ArrayList<Skyline> list = new ArrayList<>();
list.add(new Skyline(building[start].left, building[start].height));
list.add(new Skyline(building[end].right, 0));
return list;
}
int mid = (start + end) / 2;
ArrayList<Skyline> sky1 = this.findSkyline(start, mid);
ArrayList<Skyline> sky2 = this.findSkyline(mid + 1, end);
return this.mergeSkyline(sky1, sky2);
}
public ArrayList<Skyline> mergeSkyline(ArrayList<Skyline> sky1, ArrayList<Skyline> sky2) {
int currentH1 = 0, currentH2 = 0;
ArrayList<Skyline> skyline = new ArrayList<>();
int maxH = 0;
while (!sky1.isEmpty() && !sky2.isEmpty()) {
if (sky1.get(0).coordinates < sky2.get(0).coordinates) {
int currentX = sky1.get(0).coordinates;
currentH1 = sky1.get(0).height;
if (currentH1 < currentH2) {
sky1.remove(0);
if (maxH != currentH2) skyline.add(new Skyline(currentX, currentH2));
} else {
maxH = currentH1;
sky1.remove(0);
skyline.add(new Skyline(currentX, currentH1));
}
} else {
int currentX = sky2.get(0).coordinates;
currentH2 = sky2.get(0).height;
if (currentH2 < currentH1) {
sky2.remove(0);
if (maxH != currentH1) skyline.add(new Skyline(currentX, currentH1));
} else {
maxH = currentH2;
sky2.remove(0);
skyline.add(new Skyline(currentX, currentH2));
}
}
}
while (!sky1.isEmpty()) {
skyline.add(sky1.get(0));
sky1.remove(0);
}
while (!sky2.isEmpty()) {
skyline.add(sky2.get(0));
sky2.remove(0);
}
return skyline;
}
public class Skyline {
public int coordinates;
public int height;
public Skyline(int coordinates, int height) {
this.coordinates = coordinates;
this.height = height;
}
}
public class Building {
public int left;
public int height;
public int right;
public Building(int left, int height, int right) {
this.left = left;
this.height = height;
this.right = right;
}
}
public static void main(String[] args) {
SkylineProblem skylineProblem = new SkylineProblem();
skylineProblem.run();
}
}
