|
4 | 4 | importjava.util.Arrays; |
5 | 5 | importjava.util.List; |
6 | 6 | importjava.util.TreeMap; |
7 | | -/** |
8 | | - * 218. The Skyline Problem |
9 | | - * |
10 | | - * A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. |
11 | | - * Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), |
12 | | - * write a program to output the skyline formed by these buildings collectively (Figure B). |
13 | | - * |
14 | | - * The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], |
15 | | - * where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, |
16 | | - * and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. |
17 | | - * You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0. |
18 | | - * |
19 | | - * For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] . |
20 | | - * The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] |
21 | | - * that uniquely defines a skyline. |
22 | | - * A key point is the left endpoint of a horizontal line segment. |
23 | | - * Note that the last key point, where the rightmost building ends, |
24 | | - * is merely used to mark the termination of the skyline, and always has zero height. |
25 | | - * Also, the ground in between any two adjacent buildings should be considered part of the skyline contour. |
26 | | -
|
27 | | - For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]. |
28 | | -
|
29 | | - Notes: |
30 | | -
|
31 | | - The number of buildings in any input list is guaranteed to be in the range [0, 10000]. |
32 | | - The input list is already sorted in ascending order by the left x position Li. |
33 | | - The output list must be sorted by the x position. |
34 | | - There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]*/ |
35 | | - |
36 | | -/**This video is super clear and helpful: https://www.youtube.com/watch?v=GSBLe8cKu0s |
37 | | -
|
38 | | - Algorithm: |
39 | | -First observation: all the points in the final result come from the four angles that each building has |
40 | | -Scan through the horizontal lines |
41 | | -Use a PriorityQueue to hold each building, and make the PriorityQueue to sort on the height of the buildings |
42 | | -whenever we encounter the start of a building, we push it into the PriorityQueue, whenever we finished scanning that building, we remove it from the PriorityQueue |
43 | | -Also, in the scan process, we’ll keep updating the maxHeight in the PriorityQueue if we find a new maxHeight which means the building will be overshadowed by the new higher one |
44 | | -
|
45 | | -Three edge cases (see the graph illustration in the above video at 12’18”): |
46 | | -when two buildings have the same start point, the one with higher height shows up in the final result |
47 | | -when two buildings have the same end point, the one with higher height shows up in the final result |
48 | | -when the start point of one building is is also the end point of another building, the one with higher height shows up in the final result |
49 | | -
|
50 | | - We use TreeMap over a normal PriorityQueue: |
51 | | -For the sake of efficiency (better time complexity), we’ll use TreeMap which supports O(logn) for remove() operation, |
52 | | - this is the reason we choose TreeMap over a normal PriorityQueue in Java (PriorityQueue supports add() and getMaxVal() in both O(logn) time, however, for remove(), it does NOT.) |
53 | | -But TreeMap in Java supports all the three operations in O(logn) time.*/ |
54 | 7 |
|
55 | 8 | publicclass_218 { |
56 | 9 |
|
|