[LeetCode]The Skyline Problem

很经典的天际线问题，题目已经告诉了我们表示方法，我们要求出这个表示方法。最开始的想法可能是sort之后算当前interval和之前interval的交点。但是这个方法只适用于两个interval相交的情况，对于完全包含的情况，比如[0, 5, 2]和[2, 3, 3]，就无法处理了，这个方法行不通。我们再仔细看一看题目的例子，可以看出来，我们需要check的点就是所有rectangle的两个端点，对于每一个点，找当前的左右经过这一点的rectangle的最高点（不包括rectangle的最高点）。那么我们如何寻找最高点呢？很明显答案就是priority queue，每次经过左端点的时候像priority queue中插入，每次check的时候，pop掉所有pq顶端过期的点，也就是已经扫过的rectangle的右端点如果在pq顶端就pop出。然后看当前的点的高度能否加入天际线的结果集。时间复杂度O(n * log n)，代码如下：


从另一个角度看，这也是一道range query的问题。每插入一个天际线[s, e, h]就相当于把[s, e - 1]的范围内的点更新，然后对于每一个critical point我们query其最大值。用segment tree实现即可，我们所要的需求是:

• 范围更新
• 单点查询

单点查询好说。范围更新的话我们用lazy propagation即可，细节可以查看上面给出的链接。另外一个细节，因为输入building的数量最多也就10000个，point的数量最多也就20000个。尽管每个buidling对应的其实和结束端点可能很大，我们可以把所有节点对应的x坐标的值压缩到[0, 20000]范围中，这样在我们构建segment tree的时候可以省下很多空间。时间复杂度O(n * log n)，因为每次插入查询的时间复杂度都是O(log n)，代码如下：