Merge skylines, divide and conquer

Question

I'm trying to solve the famous skyline problem (see gif): Input (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28) Should return, the points that are behind other buildings should be gone and the coordinates of changes in the Y-axis should be in the returning skyline: (1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (23, 13), (29, 0) I'm trying to do so by using a divide and conquer approach to the algorithm as to achieve a running time of O(n lg n), but I'm stuck on the merge part. Everytime I think about it I get confused. For example, I check which one the skylines is first e.g. which has the lower x-coordinate, then I add that + its hight to my new skyline. But then I encounter a skyline thats behind two other skylines, how can I detect this 'collision'? Do I first check if the skylines have any overlap by checking if left.x2 < right.x1? But then I think what should I check first? Overlap of precedence on the x-axis and everything tu…

Accepted Answer

I think this should be an approach that's easier to wrap one's head around:

Split x-coordinates into start and finish objects for each rectangle, as follows:

```
rect(x1, y, x2) -> (x1, y, "start", reference to rect),
                   (x2, y, "finish", reference to rect)
```

So something like:

```
class MyStruct
{
   Rectangle rect;
   int x, y;
   bool isStart;
}
```

- Sort these objects by x-coordinate (`O(n log n)`)

- Create an (intially empty) set of rectangles (which will be sorted by y-coordinate, e.g. a BST)

- Loop through these objects (in the now-sorted order) (`O(n)`)

- Whenever a start is encountered

- Add the rectangle to the set of rectangles (`O(log n)`)

- If it's the new highest rectangle, add that start point to the output (`O(1)`)

- Whenever a finish is encountered

- Remove the rectangle from the set of rectangles (`O(log n)`)

- If it's the highest rectangle, find the next highest rectangle in the set and add the point `(current.finishX, new.y)` to the output (`O(1)`) (if the set is empty, add `(current.finishX, 0)` to the output instead)

So `O(n log n)`.

Merge skylines, divide and conquer

Solution

Problem