我试图解决这个著名的天际线的问题（见GIF）：

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）

(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)

应该返回，这是其他建筑应消失和改变Y轴坐标的背后应该是在返回天际线的点：

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）

(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (23, 13), (29, 0)

我想用除法的话而治之的​​方法来算法实现为O（n LG N）的运行时间，但我卡在合并的部分。

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.

每当我想到我感到困惑。例如，我检查哪一个天际线是第一个如它具有较低的x坐标，然后我再补充一点+其HIGHT到我的新天际线。但后来我遇到落后另外两个天际线天际线，多数民众赞成，我怎么可以检测到这种冲突？

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'?

难道我首先检查的天际线有任何重叠，通过检查left.x2＆LT; right.x1？但后来我想，我应该先检查？在x轴precedence和重叠的一切变成了一个大鸡先有蛋的混乱。

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 turns into a big chicken-egg mess.

也许我在想太复杂？我需要的是设定最高y坐标，在每一个路口，我应该接近它这样吗？

Maybe I'm thinking too complicated? What I need is the set of highest y coordinates, at every intersection, should I approach it like this?

推荐答案

我想这应该是一种方法，更容易包裹周围人的头：

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

拆分x坐标转化为每个矩形的开始和结束对象，如下所示：

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;
}

排序这些对象通过X坐标（为O（n log n）的） 创建一个（intially空）组矩形（将被排序y坐标，例如，一个 BST ） 在遍历这些对象（在现在的排序顺序）（ O（N）） 在每次启动时遇到 矩形添加到组矩形（ O（log n）的） 如果它是新的最高矩形，即起点添加到输出（ O（1））

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))

从矩形集合中删除的矩形（ O（log n）的） 如果它是最高的矩形，发现该组中的下一个最大的矩形，并添加点（current.finishX，new.y）到输出（ 0（1））（如果设置为空，添加（current.finishX，0）的输出，而不是） 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)

所以为O（n log n）的。