HARD/src/hard/TheSkylineProblem.java

fishercoder1534 · fishercoder1534 · commit 102751c82a9c · 2016-09-28T23:13:58.000-07:00
diff --git a/HARD/src/hard/TheSkylineProblem.java b/HARD/src/hard/TheSkylineProblem.java
@@ -4,6 +4,25 @@
 import java.util.Arrays;
 import java.util.List;
 import java.util.TreeMap;
+/**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 TheSkylineProblem {
 
