The skyline of a city is the outer outline of all the buildings in the city as viewed from a distance. To give you the location and height of all the buildings, return to the skyline formed by these buildings.

The geometric information of each building is represented by the array buildings, where the triad buildings[I] = [lefti, righti, Heighti] is represented by:

  • Lefti is the x coordinate of the left edge of building I.
  • Righti is the X coordinate of the right edge of building I.
  • Heighti is the height of the ith building.

The skyline should be represented as a list of “key points” in the format [[X1,y1],[x2,y2],… And sort them by the x coordinate. The key point is the left end of the horizontal segment. The last point in the list is the end of the right-most building, and the y-coordinate is always 0, used only to mark the end of the skyline. In addition, the ground between any two adjacent buildings should be considered part of the skyline profile.

Note: the output skyline must not have consecutive horizontal lines of the same height. For example, […[2 3], [4 5], [7 5], [11 5], [12 7]… Is the wrong answer; Three height is 5 lines should be in the final output into a: [… [2, 3], [4, 5], [7],…

  • Example 1:

  

Input: buildings = [,9,10 [2], [3,7,15], [5,12,12], [15, 10], [19,24,8]] output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]] explanation: figure A shows the positions and heights of all the buildings entered, and figure B shows the skyline formed by these buildings. The red dots in Figure B represent key points in the output list. Example 2: input: buildings = [[0, 2, 3], [2,5,3]] output: [[0, 3], [5, 0]]Copy the code

Their thinking

We can see from observation that

  • The key points always come from the left or right edge of the building
  • There must be a height difference between two adjacent key points

Therefore, we can traverse only the left and right edges of all buildings, and the key points are generated only in these points

Since the key points of the final result need to be sorted according to the X coordinate, we first sorted the left and right endpoints of all buildings in a unified order from small to large according to the X coordinate. If the X coordinate is the same, we sorted them according to the height from small to large

To distinguish the left and right ends of a building, we can use a negative number to represent the height of the left end and a positive number to represent the height of the right end

Suppose we walk to an endpoint cur, and the big top heap stores the x coordinate of that endpoint, which is represented by several buildingsFor example, x = 7, storage is the height of the three buildings, because the current traversal is red right endpoints of the building, so in the current coordinates of x = 7, is no longer be overwritten, so is the height of the two buildings, and the maximum height of the building is 12, and the key points before the maximum height of inconsistencies, so you can judge the key point

conclusion

In simple terms, in the process of traverse of the endpoints, done by plus or minus the height of the buildings around the endpoint of the judgment, entering a priority queue, endpoint traversal to left behind that several of the x coordinates are covered by the current height of h building, the right endpoints of traverse to retreat to a priority queue, that behind all the x coordinates are not covered by the current height of h building. So with the priority queue, we know how many buildings are covered by the x coordinate of the current endpoint, because the tallest building will overshadow the other low buildings, so we maintain a big top heap.

Since the height of the key point is necessarily different from that of the previous key point, as long as the height of the current heap top element is different from that of the previous key point, we can determine that the current x coordinate is also a key point

code

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> res=new ArrayList<>();
        List<int[]> cnt=new ArrayList<>();
        for (int[] building : buildings) {
            cnt.add(new int[]{building[0],-building[2]});
            cnt.add(new int[]{building[1],building[2]});
        }
        int i=0,pre=0;

        Collections.sort(cnt,(o1, o2) -> o1[0]==o2[0]? o1[1]-o2[1]:o1[0]-o2[0]);
        PriorityQueue<Integer>priorityQueue=new PriorityQueue<>((o1, o2) -> o2-o1);
        priorityQueue.add(0);
        for (int[] cur : cnt) {

            if(cur[1] <0){
                priorityQueue.add(-cur[1]);
            }else{
                priorityQueue.remove(cur[1]);
            }
            int h=priorityQueue.peek();
            if(h! =pre) { res.add(Arrays.asList(cur[0],h)); pre=h; }}returnres; }}Copy the code