合并天际线，分而治之

问题描述：

我试图解决这个著名的天际线的问题（见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))

相关推荐