JavaAlgorithms/Others/SkylineProblem.java

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();
  }
}