[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)，代码如下：

	class Solution {
	public:
	vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
	vector<tuple<int, int, int>> criticalPoints;
	for(auto&& building : buildings)
	{
	criticalPoints.push_back(make_tuple(building[0], building[2], building[1]));
	criticalPoints.push_back(make_tuple(building[1], -1, -1));
	}
	auto comp = [](const tuple<int, int, int>& lhs, const tuple<int, int, int>& rhs){return get<0>(lhs) == get<0>(rhs)? get<1>(lhs) > get<1>(rhs): get<0>(lhs) < get<0>(rhs);};
	sort(criticalPoints.begin(), criticalPoints.end(), comp);
	priority_queue<pair<int, int>> heights;
	vector<pair<int, int>> res;
	for(auto&& point : criticalPoints)
	{
	while(heights.size() && heights.top().second <= get<0>(point))heights.pop();
	if(get<2>(point) >= 0)heights.push({get<1>(point), get<2>(point)});
	int currHeight = heights.empty()? 0: heights.top().first;
	if(res.empty() || currHeight != res.back().second)res.push_back({get<0>(point), currHeight});
	}
	return res;
	}
	};

view raw The Skyline Problem.cpp hosted with ❤ by GitHub

从另一个角度看，这也是一道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)，代码如下：

	struct Node
	{
	int val, lazy;
	Node()
	{
	val = 0;
	lazy = 0;
	}
	Node(int v)
	{
	val = v;
	lazy = 0;
	}
	};
	class ST
	{
	public:
	ST(int n)
	{
	N = n;
	tree = vector<Node>(3 * N);
	}
	void insert(int lo, int hi, int val)
	{
	insert(0, 0, N - 1, lo, hi, val);
	}
	int query(int key)
	{
	return query(0, key, 0, N - 1);
	}
	private:
	int N;
	vector<Node> tree;
	void insert(int i, int clo, int chi, int lo, int hi, int val)
	{
	if (tree[i].lazy)propagate(i, chi - clo + 1);
	if (clo > hi || chi < lo)return;
	else if (clo >= lo && chi <= hi)
	{
	tree[i].val = max(val, tree[i].val);
	if (clo != chi)
	{
	tree[2 * i + 1].lazy = max(val, tree[2 * i + 1].lazy);
	tree[2 * i + 2].lazy = max(val, tree[2 * i + 2].lazy);
	}
	}
	else
	{
	int mid = clo + (chi - clo) / 2;
	insert(2 * i + 1, clo, mid, lo, hi, val);
	insert(2 * i + 2, mid + 1, chi, lo, hi, val);
	}
	}
	int query(int i, int key, int lo, int hi)
	{
	if (tree[i].lazy)propagate(i, hi - lo + 1);
	if (hi == lo)return tree[i].val;
	int mid = lo + (hi - lo) / 2;
	if (key <= mid)return query(2 * i + 1, key, lo, mid);
	else return query(2 * i + 2, key, mid + 1, hi);
	}
	void propagate(int i, int len)
	{
	if (len != 1)
	{
	tree[2 * i + 1].lazy = max(tree[i].lazy, tree[2 * i + 1].lazy);
	tree[2 * i + 2].lazy = max(tree[i].lazy, tree[2 * i + 2].lazy);
	}
	tree[i].val = max(tree[i].lazy, tree[i].val);
	tree[i].lazy = 0;
	}
	};
	class Solution {
	public:
	vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
	int len = buildings.size();
	ST st(20005);
	vector<int> xs;
	//range compression
	for (const auto& building : buildings)
	{
	int start = building[0], end = building[1];
	xs.push_back(start);
	xs.push_back(end - 1);
	xs.push_back(end);
	}
	sort(xs.begin(), xs.end());
	unordered_map<int, int> xMap;
	for (int i = 0; i < xs.size(); ++i)xMap[xs[i]] = i;
	for (const auto& building : buildings)
	{
	int start = xMap[building[0]], end = xMap[building[1] - 1], height = building[2];
	st.insert(start, end, height);
	}
	vector<pair<int, int>> res;
	for (const auto& x : xs)
	{
	int h = st.query(xMap[x]);
	if (res.size() && res.back().second == h)continue;
	res.emplace_back(x, h);
	}
	return res;
	}
	};

view raw The Skyline Problem.cpp hosted with ❤ by GitHub