Skyline Problem in Java

The skyline of a city is the outer edge of the pattern created by all of its structures when viewed from a distance. Return the skyline that these buildings together create based on their positions and heights.

Assuming n rectangular buildings in a two-dimensional cityscape, evaluates their skylines while ignoring hidden lines. The main goal is to look at structures from different angles and eliminate any elements that are not visible.

Each structure has a common bottom and is represented by a triplet (left, height, right)

• left: on the left side is x coordinated (or wall).
• right: is the right side's x coordinate.
• height: is the building's height.

The skyline is made up of rectangular strips. A rectangular strip is represented as a pair (left, height), where left seems to be the x coordinate of the strip's left side and ht is the strip's height.

All structures are assumed to be perfect rectangles grounded on a completely uniform surface at height 0.

The skyline should be represented as a list of "key points" ordered by x-coordinate in the format [[x1,y1],[x2,y2],...]. Except for the last point in the list, which always has a y-coordinate of 0 and is used to denote the skyline's conclusion where the rightmost building finishes, each key point is the left endpoints of some horizontal segment in the skyline. Any land between the left and rightmost buildings should be included in the outline of the skyline.

Example1:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

Explanation:

Figure A displays the input's buildings.

Figure B depicts the skyline generated by these structures. The red dots in picture B reflect the output list's main points.

Example2:

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]

Approach:

1. Retrieve the left wall position, height, and right wall location values for each structure from the triplets that have been provided.
2. Keep the pair of the right wall's real height and the left wall's negative height value in a vector called walls. The left and right walls of the same structure are divided in this way.
3. Sort the walls from highest to lowest.
4. If a left wall is located while traversing the vector walls, record its height in the multiset. If a right wall is found in any other case, take the multiset's equivalent height accordingly.
5. Verify whether or not the top value has changed. If it has changed, update the top value and save the abscissa(x-coordinate) value of the current wall together with the revised top value in a vector designated as the skyline.
6. The value pairs kept in the skyline vector should be printed.

Filename: Skyline.java

class Skyline {
  public List<List<Integer>> getSkyline(int[][] buildings) {
    final int a = buildings.length;
    if (a == 0)
      return new ArrayList<>();
    if (a == 1) {
      final int left = buildings[0][0];
      final int right = buildings[0][1];
      final int height = buildings[0][2];
      List<List<Integer>> ans = new ArrayList<>();
      ans.add(new ArrayList<>(Arrays.asList(left, height)));
      ans.add(new ArrayList<>(Arrays.asList(right, 0)));
      return ans;
    }
    List<List<Integer>> leftSkyline = getSkyline(Arrays.copyOfRange(buildings, 0, a / 2));
    List<List<Integer>> rightSkyline = getSkyline(Arrays.copyOfRange(buildings, a / 2, a));
    return merge(leftSkyline, rightSkyline);
  }
  private List<List<Integer>> merge(List<List<Integer>> left, List<List<Integer>> right) {
    List<List<Integer>> ans = new ArrayList<>();
    int u = 0; // left's index
    int v = 0; // right's index
    int leftY = 0;
    int rightY = 0;
    while (u < left.size() && v < right.size())
      // Choose the point with smaller x
      if (left.get(u).get(0) < right.get(v).get(0)) {
        leftY = left.get(u).get(1); // Update the ongoing leftY
        addPoint(ans, left.get(u).get(0), Math.max(left.get(u++).get(1), rightY));
      } else {
        rightY = right.get(v).get(1); // Update the ongoing rightY
        addPoint(ans, right.get(v).get(0), Math.max(right.get(v++).get(1), leftY));
      }
    while (u < left.size())
      addPoint(ans, left.get(u).get(0), left.get(u++).get(1));
    while (v < right.size())
      addPoint(ans, right.get(v).get(0), right.get(v++).get(1));
    return ans;
  }
  private void addPoint(List<List<Integer>> ans, int p, int q) {
    if (!ans.isEmpty() && ans.get(ans.size() - 1).get(0) == p) {
      ans.get(ans.size() - 1).set(1, q);
      return;
    }
    if (!ans.isEmpty() && ans.get(ans.size() - 1).get(1) == q)
      return;
    ans.add(new ArrayList<>(Arrays.asList(p, q)));
  }
}

Output:

buildings =
[[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
 [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

Filename: Skyline.java

class Skyline {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> heightList = new LinkedList<List<Integer>>();
        TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
        List<List<Integer>> alpha = new LinkedList<List<Integer>>();
        int PreviousHeight = 0;        
        for(int[] A : buildings) {
            heightList.add(Arrays.asList(A[0], -A[2]));
            heightList.add(Arrays.asList(A[1], A[2]));
        }
        Collections.sort(heightList, (x, y)->(x.get(0).intValue() != y.get(0).intValue() ? x.get(0) - y.get(0) : x.get(1) - y.get(1)));
        map.put(0, 1);
        for(List<Integer> A : heightList) {
            int Height = A.get(1);
            if(Height < 0)map.put(-Height, map.getOrDefault(-Height, 0) + 1);
            else if(map.getOrDefault(Height, 0) > 1)map.put(Height, map.get(Height) - 1);
            else map.remove(Height);
            if(map.lastKey() != PreviousHeight) {
                PreviousHeight = map.lastKey();
                alpha.add(Arrays.asList(A.get(0), PreviousHeight));
            }
        }
        return alpha;
    }
}

Output:

buildings =
[[0,2,3],[2,5,3]]
 [[0,3],[5,0]]