Skyline Problem (Leetcode 218, Lintcode 131)

一道经典的面试题。这道题在Leetcode上被列为Hard，而在Lintcode上被列为Super，不过掌握要点后就还好。

要点

1. c++中，用multiset建立priority_queue, 以便于删除

2. 利用扫描线的算法，将输入拆分成起点终点段。扫描时，如果是起点，加入pque，如果是终点，则将该点高度从pque中删除。而每次遇到一个点，都从pque中取出最大值process。

3. 如果是起点，就把高度按照负数存放，这是为了处理overlap的情况。同一个点的起点，应该由高到低排序。同一个点的终点，应该由低到高排序。同时，先起点，再终点。

multiset的用法：

multiset<int, greater<int>> st; //max heap建立
st.erase(st.find(20)) // 删除

class Solution {
public:
    
    struct Edge{
       int x, height;
       bool isStart;
       Edge(int x_, int h_, bool i_) : x(x_), height(h_), isStart(i_){}
    };
    
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int, int>> ret;
        if(buildings.empty()) return ret;
        vector<Edge> Edges;
        for(auto it : buildings){
            Edges.push_back(Edge(it[0], -it[2], true));
            Edges.push_back(Edge(it[1], it[2], false));
        }
        
        auto comp = [](const Edge &e1, const Edge &e2){
            if(e1.x == e2.x){
                return e1.height < e2.height;
            }
            return e1.x < e2.x;
        };
        
        sort(Edges.begin(), Edges.end(), comp);
        
        multiset<int, greater<int>> st;
        int pre = 0;
        for(auto it : Edges){
            if(it.isStart){
                st.insert(-it.height);
            }
            else{
                st.erase(st.find(it.height));
            }
            int cur = *st.begin();
            if(cur != pre){
                ret.push_back({it.x, cur});
                pre = cur;
            }
        }
        return ret;
        
    }
};

Lintcode的要求更高一些，需要输出新的skyline边，而不是skyline点。而要点就是新增一个变量，来记录上一个点的x坐标

class Solution {
public:
    /**
     * @param buildings: A list of lists of integers
     * @return: Find the outline of those buildings
     */
    struct Edge{
       int x, height;
       bool isStart;
       Edge(int x_, int h_, bool i_) : x(x_), height(h_), isStart(i_){}
    };
    vector<vector<int>> buildingOutline(vector<vector<int>> &buildings) {
        // write your code here
        vector<vector<int>> ret;
        if(buildings.empty()) return ret;
        
        vector<Edge> Edges;
        for(auto it : buildings){
            Edges.push_back(Edge(it[0], -it[2], true));
            Edges.push_back(Edge(it[1], it[2], false));
        }
        
        auto comp = [](const Edge &e1, const Edge &e2){
            if(e1.x == e2.x){
                return e1.height < e2.height;
            }
            return e1.x < e2.x;
        };
        
        sort(Edges.begin(), Edges.end(), comp);
        multiset<int, greater<int>> st;
        int pre = 0, prex = 0;
        
        for(auto e : Edges){
            if(e.isStart){
                st.insert(-e.height);
            }
            else{
                st.erase(st.find(e.height));
            }
            int cur = *st.begin();
            if(cur != pre){
                if(pre != 0){
                    ret.push_back({prex, e.x, pre});
                }
                prex = e.x;
                pre = cur;
            }
        }
        return ret;
    }
};