C++ Solution using multiset


  • 0

    class Solution {
    private:
    struct Compare {
    bool operator()(int x, int y) {
    return x > y;
    }
    };
    multiset<int, Compare> myset;
    struct Node {
    int val;
    int pos;
    bool is_start;
    Node(int pos, int val, bool is_start) {
    this -> val = val;
    this -> pos = pos;
    this -> is_start = is_start;
    }
    };
    static bool compare(Node n1, Node n2) {
    if(n1.pos == n2.pos) {
    if(n1.is_start && n2.is_start) {
    return n1.val > n2.val;
    }
    if(!n1.is_start && !n2.is_start) {
    return n1.val < n2.val;
    }
    return n1.is_start;
    }else {
    return n1.pos < n2.pos;
    }
    }
    void eraseset(int value) {
    auto it = myset.begin();
    while(it != myset.end()) {
    if(*it == value) {
    myset.erase(it);
    break;
    }
    it++;
    }
    }
    public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
    vector<Node> nodes;
    for(auto it : buildings) {
    nodes.push_back(Node(it[0], it[2], true));
    nodes.push_back(Node(it[1], it[2], false));
    }
    sort(nodes.begin(), nodes.end(), compare);
    myset.insert(0);
    vector<pair<int, int>> res;
    int curmax = 0;
    for(auto it : nodes) {
    if(it.is_start) {
    if(it.val > curmax) {
    curmax = it.val;
    res.push_back(make_pair(it.pos, it.val));
    }
    myset.insert(it.val);
    }else {
    eraseset(it.val);
    if(it.val == curmax) {
    if(*myset.begin() != curmax) {
    res.push_back(make_pair(it.pos, *myset.begin()));
    }
    curmax = *myset.begin();
    }
    }
    }
    return res;
    }
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.