skyline problem

1）edge数组的排序，pos > start or not > height

2）mulitiset可以放多个相同的element，是一个树，然后key=value，最后要删除多个相同元素中的其中一个要用，mulset.erase(mulset.lower_bound(value));

3）选择最后（最大）的一个元素的方法：*multiset.rbegin();

class edge {
public:
    int pos;
    int height;
    bool isStart;
    edge(int pos, int height, bool isStart)
    {
        this->pos = pos;
        this->height = height;
        this->isStart = isStart;
    }
};

bool comp(edge e1, edge e2)
{
    if(e1.pos != e2.pos)
    {
        return e1.pos < e2.pos;
    }

    if(e1.isStart && e2.isStart)
    {
        return e1.height > e2.height;
    }

    if(!e1.isStart && !e2.isStart)
    {
        return e1.height < e2.height;
    }

    return e1.isStart;
}

class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        int n = buildings.size();
        vector<pair<int, int>> ret;
        if(n == 0)
        {
            return ret;
        }

        vector<edge> edges;
        for(vector<int> build : buildings)
        {
            edges.push_back(edge(build[0], build[2], true));
            edges.push_back(edge(build[1], build[2], false));
        }

        sort(edges.begin(), edges.end(), comp);

        multiset<int> hash;

        for(edge e : edges)
        {
            //cout<<e.pos<<" "<<e.height<<" "<<e.isStart<<endl;
            //cout<<hash.size()<<endl;
            if(e.isStart)
            {
                if(hash.empty() || e.height > *hash.rbegin())
                {
                    ret.push_back(make_pair(e.pos, e.height));
                }
                hash.insert(e.height);
            }
            else
            {
                hash.erase(hash.lower_bound(e.height));
                if(hash.size() == 0)
                {
                    ret.push_back(make_pair(e.pos, 0));
                    continue;
                }

                if(e.height > *hash.rbegin())
                {
                    ret.push_back(make_pair(e.pos, *hash.rbegin()));
                }
            }
        }

        return ret;
    }
};