refactor 218

fishercoder1534 · fishercoder1534 · commit 002f0b6afdf9 · 2020-05-15T07:18:21.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_218.java b/src/main/java/com/fishercoder/solutions/_218.java
@@ -4,53 +4,6 @@
 import java.util.Arrays;
 import java.util.List;
 import java.util.TreeMap;
-/**
- * 218. The Skyline Problem
- *
- * A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance.
- * Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A),
- * write a program to output the skyline formed by these buildings collectively (Figure B).
- *
- * The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi],
- * where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively,
- * and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0.
- * You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
- *
- * 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] ] .
- * The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ]
- * that uniquely defines a skyline.
- * A key point is the left endpoint of a horizontal line segment.
- * Note that the last key point, where the rightmost building ends,
- * is merely used to mark the termination of the skyline, and always has zero height.
- * Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
-
- 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] ].
-
- Notes:
-
- The number of buildings in any input list is guaranteed to be in the range [0, 10000].
- The input list is already sorted in ascending order by the left x position Li.
- The output list must be sorted by the x position.
- 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], ...]*/
-
-/**This video is super clear and helpful: https://www.youtube.com/watch?v=GSBLe8cKu0s
-
- Algorithm:
-First observation: all the points in the final result come from the four angles that each building has
-Scan through the horizontal lines
-Use a PriorityQueue to hold each building, and make the PriorityQueue to sort on the height of the buildings
-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
-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
- 
-Three edge cases (see the graph illustration in the above video at 12’18”):
-when two buildings have the same start point, the one with higher height shows up in the final result
-when two buildings have the same end point, the one with higher height shows up in the final result
-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
-
- We use TreeMap over a normal PriorityQueue:
-For the sake of efficiency (better time complexity), we’ll use TreeMap which supports O(logn) for remove() operation,
- 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.)
-But TreeMap in Java supports all the three operations in O(logn) time.*/
 
 public class _218 {
 
