|
4 | 4 | importjava.util.Arrays; |
5 | 5 | importjava.util.List; |
6 | 6 | importjava.util.TreeMap; |
| 7 | +/**This video is super clear and helpful: https://www.youtube.com/watch?v=GSBLe8cKu0s |
| 8 | +
|
| 9 | + Algorithm: |
| 10 | +First observation: all the points in the final result come from the four angles that each building has |
| 11 | +Scan through the horizontal lines |
| 12 | +Use a PriorityQueue to hold each building, and make the PriorityQueue to sort on the height of the buildings |
| 13 | +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 |
| 14 | +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 |
| 15 | +
|
| 16 | +
|
| 17 | +Three edge cases (see the graph illustration in the above video at 12’18”): |
| 18 | +when two buildings have the same start point, the one with higher height shows up in the final result |
| 19 | +when two buildings have the same end point, the one with higher height shows up in the final result |
| 20 | +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 |
| 21 | +
|
| 22 | +
|
| 23 | + We use TreeMap over a normal PriorityQueue: |
| 24 | +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.) |
| 25 | +But TreeMap in Java supports all the three operations in O(logn) time.*/ |
7 | 26 |
|
8 | 27 | publicclassTheSkylineProblem { |
9 | 28 |
|
|