SkylineProblem.java

packagecom.thealgorithms.others;

importjava.util.ArrayList;

/**
 * The {@code SkylineProblem} class is used to solve the skyline problem using a
 * divide-and-conquer approach.
 * It reads input for building data, processes it to find the skyline, and
 * prints the skyline.
 */
publicclassSkylineProblem {

Building[] building;
intcount;

/**
 * Adds a building with the given left, height, and right values to the
 * buildings list.
 *
 * @param left The left x-coordinate of the building.
 * @param height The height of the building.
 * @param right The right x-coordinate of the building.
 */
publicvoidadd(intleft, intheight, intright) {
building[count++] = newBuilding(left, height, right);
 }

/**
 * Computes the skyline for a range of buildings using the divide-and-conquer
 * strategy.
 *
 * @param start The starting index of the buildings to process.
 * @param end The ending index of the buildings to process.
 * @return A list of {@link Skyline} objects representing the computed skyline.
 */
publicArrayList<Skyline> findSkyline(intstart, intend) {
// Base case: only one building, return its skyline.
if (start == end) {
ArrayList<Skyline> list = newArrayList<>();
list.add(newSkyline(building[start].left, building[start].height));
list.add(newSkyline(building[end].right, 0)); // Add the end of the building
returnlist;
 }

intmid = (start + end) / 2;

ArrayList<Skyline> sky1 = this.findSkyline(start, mid); // Find the skyline of the left half
ArrayList<Skyline> sky2 = this.findSkyline(mid + 1, end); // Find the skyline of the right half
returnthis.mergeSkyline(sky1, sky2); // Merge the two skylines
 }

/**
 * Merges two skylines (sky1 and sky2) into one combined skyline.
 *
 * @param sky1 The first skyline list.
 * @param sky2 The second skyline list.
 * @return A list of {@link Skyline} objects representing the merged skyline.
 */
publicArrayList<Skyline> mergeSkyline(ArrayList<Skyline> sky1, ArrayList<Skyline> sky2) {
intcurrentH1 = 0;
intcurrentH2 = 0;
ArrayList<Skyline> skyline = newArrayList<>();
intmaxH = 0;

// Merge the two skylines
while (!sky1.isEmpty() && !sky2.isEmpty()) {
if (sky1.get(0).coordinates < sky2.get(0).coordinates) {
intcurrentX = sky1.get(0).coordinates;
currentH1 = sky1.get(0).height;

if (currentH1 < currentH2) {
sky1.remove(0);
if (maxH != currentH2) {
skyline.add(newSkyline(currentX, currentH2));
 }
 } else {
maxH = currentH1;
sky1.remove(0);
skyline.add(newSkyline(currentX, currentH1));
 }
 } else {
intcurrentX = sky2.get(0).coordinates;
currentH2 = sky2.get(0).height;

if (currentH2 < currentH1) {
sky2.remove(0);
if (maxH != currentH1) {
skyline.add(newSkyline(currentX, currentH1));
 }
 } else {
maxH = currentH2;
sky2.remove(0);
skyline.add(newSkyline(currentX, currentH2));
 }
 }
 }

// Add any remaining points from sky1 or sky2
while (!sky1.isEmpty()) {
skyline.add(sky1.get(0));
sky1.remove(0);
 }

while (!sky2.isEmpty()) {
skyline.add(sky2.get(0));
sky2.remove(0);
 }

returnskyline;
 }

/**
 * A class representing a point in the skyline with its x-coordinate and height.
 */
publicclassSkyline {
publicintcoordinates;
publicintheight;

/**
 * Constructor for the {@code Skyline} class.
 *
 * @param coordinates The x-coordinate of the skyline point.
 * @param height The height of the skyline at the given coordinate.
 */
publicSkyline(intcoordinates, intheight) {
this.coordinates = coordinates;
this.height = height;
 }
 }

/**
 * A class representing a building with its left, height, and right
 * x-coordinates.
 */
publicclassBuilding {
publicintleft;
publicintheight;
publicintright;

/**
 * Constructor for the {@code Building} class.
 *
 * @param left The left x-coordinate of the building.
 * @param height The height of the building.
 * @param right The right x-coordinate of the building.
 */
publicBuilding(intleft, intheight, intright) {
this.left = left;
this.height = height;
this.right = right;
 }
 }
}