c# - 合并天际线，划分并征服

我正试图解决著名的天际线问题（见gif）：
输入
（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轴的坐标应该在返回的天际线中：
（1，11），（3，13），（9，0），（12，7），（16，3），（19，18），（22，3），（23，13），（29，0）
我试图用分而治之的方法来实现算法的运行时间为o（n lgn），但是我陷入了合并的问题。
每当我想到它，我就会感到困惑。例如，我先检查哪一个是天际线，例如哪一个有较低的x坐标，然后将其+其高度添加到我的新天际线。但当我遇到另两个天际线后面的天际线时，我怎么能察觉到这种“碰撞”？
我是否首先通过检查left.x2也许我想的太复杂了？我需要的是一组最高的y坐标，在每个交叉点，我应该这样接近它吗？

最佳答案

我认为这应该是一种更容易理解的方法：
将每个矩形的x坐标拆分为开始和结束对象，如下所示：

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

比如说：

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

按x坐标对这些对象排序（O(n log n)）
创建一组（最初为空）矩形（将按y坐标排序，例如aBST）
循环遍历这些对象（按现在排序的顺序）（小于cc>）
每当遇到开始时
将矩形添加到矩形集（O(n)）
如果是新的最高矩形，则将该起点添加到输出（O(log n)）
每当遇到终点时
从矩形集中删除矩形（O(1)）
如果是最高的矩形，则在集合中找到下一个最高的矩形，并将点O(log n)添加到输出（(current.finishX, new.y)）（如果集合为空，则将O(1)添加到输出）
所以(current.finishX, 0)。