The Skyline Problem Solutions in C++

// Source : https://leetcode.com/problems/the-skyline-problem/
// Author : Hao Chen
// Date   : 2015-06-11





/*
 * Sweep line with max-heap
 * ------------------------
 * Notice that "key points" are either the left or right edges of the buildings. 
 * 
 * Therefore, we first obtain both the edges of all the N buildings, and store the 2N edges in a sorted array. 
 * Maintain a max-heap of building heights while scanning through the edge array: 
 * 1) If the current edge is a left edge, then add the height of its associated building to the max-heap; 
 * 2) If the edge is a right one, remove the associated height from the heap. 
 * 
 * Then we take the top value of the heap (yi) as the maximum height at the current edge position (xi). 
 * Now (xi, yi) is a potential key point. 
 * 
 * If yi is the same as the height of the last key point in the result list, it means that this key point 
 * is not a REAL key point, but rather a horizontal continuation of the last point, so it should be discarded; 
 * 
 * otherwise, we add (xi,yi) to the result list because it is a real key point. 
 * 
 * Repeat this process until all the edges are checked.
 * 
 * It takes O(NlogN) time to sort the edge array. For each of the 2N edges, 
 * it takes O(1) time to query the maximum height but O(logN) time to add 
 * or remove elements. Overall, this solution takes O(NlogN) time.
 */
class Solution {
public:

    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector< pair<int, int> > edges;
        
        //put all of edge into a vector
        //set left edge as negtive, right edge as positive
        //so, when we sort the edges, 
        //  1) for same left point, the height would be descending order
        //  2) for same right point, the height would be ascending order
        int left, right, height;
        for(int i=0; i<buildings.size(); i++) {
            left   = buildings[i][0];
            right  = buildings[i][1];
            height = buildings[i][2];
            edges.push_back(make_pair(left, -height));
            edges.push_back(make_pair(right, height));
        }
        sort(edges.begin(), edges.end());

        // 1) if we meet a left edge, then we add its height into a `set`.
        //    the `set` whould sort the height automatically.
        // 2) if we meet a right edge, then we remove its height from the `set`
        //
        // So, we could get the current highest height from the `set`, if the 
        // current height is different with preivous height, then we need add
        // it into the result.
        vector< pair<int, int> > result;
        multiset<int> m;
        m.insert(0);
        int pre = 0, cur = 0;
        for (int i=0; i<edges.size(); i++){
            pair<int,int> &e = edges[i];
            if (e.second < 0) {
                m.insert(-e.second);
            }else{
                m.erase(m.find(e.second));
            }
            cur = *m.rbegin();
            if (cur != pre) {
                result.push_back(make_pair(e.first, cur));
                pre = cur;
            }
        }
        return result;

    }
};

/// Source : https://leetcode.com/problems/the-skyline-problem/description/
/// Author : liuyubobobo
/// Time   : 2017-10-28
/// updated: 2019-03-14

#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
#include <cassert>

using namespace std;


/// Using Segment Tree
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class SegmentTree{

private:
    int n;
    vector<int> tree, lazy;

public:
    SegmentTree(int n): n(n), tree(4 * n, 0), lazy(4 * n, 0){}

    void add(int l, int r, int h){
        update(0, 0, n-1, l, r, h);
    }

    int query(int index){
        return query(0, 0, n-1, index);
    }

private:
    void update(int treeID, int treeL, int treeR, int l, int r, int h){

        if(lazy[treeID] != 0){
            tree[treeID] = max(tree[treeID], lazy[treeID]); // max
            if(treeL != treeR){
                lazy[2 * treeID + 1] = max(lazy[treeID], lazy[2 * treeID + 1]); // max
                lazy[2 * treeID + 2] = max(lazy[treeID], lazy[2 * treeID + 2]); // max
            }
            lazy[treeID] = 0;
        }

        if(treeL == l && treeR == r){
            tree[treeID] = max(tree[treeID], h); // max
            if(treeL != treeR){
                lazy[2 * treeID + 1] = max(h, lazy[2 * treeID + 1]); // max
                lazy[2 * treeID + 2] = max(h, lazy[2 * treeID + 2]); // max
            }
            return;
        }

        int mid = (treeL + treeR) / 2;

        if(r <= mid)
            update(2 * treeID + 1, treeL, mid, l, r, h);
        else if(l >= mid + 1)
            update(2 * treeID + 2, mid + 1, treeR, l, r, h);
        else{
            update(2 * treeID + 1, treeL, mid, l, mid, h);
            update(2 * treeID + 2, mid + 1, treeR, mid + 1, r, h);
        }

        return;
    }

    int query(int treeID, int treeL, int treeR, int index){

        if(lazy[treeID] != 0){
            tree[treeID] = max(tree[treeID], lazy[treeID]); // max
            if(treeL != treeR){
                lazy[2 * treeID + 1] = max(lazy[treeID], lazy[2 * treeID + 1]); // max
                lazy[2 * treeID + 2] = max(lazy[treeID], lazy[2 * treeID + 2]); // max
            }
            lazy[treeID] = 0;
        }

        if(treeL == treeR){
            assert(treeL == index);
            return tree[treeID];
        }

        int mid = (treeL + treeR) / 2;

        if(index <= mid)
            return query(2 * treeID + 1, treeL, mid, index);

        return query(2 * treeID + 2, mid + 1, treeR, index);
    }
};


class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {

        // Coordinate compression
        set<int> unique_points;
        for(const vector<int>& info: buildings){
            unique_points.insert(info[0]);
            unique_points.insert(info[1]-1);
            unique_points.insert(info[1]);
        }

        unordered_map<int, int> indexes;
        vector<int> pos;
        for(int p: unique_points){
            indexes[p] = pos.size();
            pos.push_back(p);
        }

        // segment tree
        SegmentTree stree(pos.size());
        for(const vector<int>& info: buildings)
            stree.add(indexes[info[0]], indexes[info[1]-1], info[2]);

        // get results
        vector<pair<int, int>> res;
        unique_points.clear();
        for(const vector<int>& info: buildings){
            unique_points.insert(info[0]);
            unique_points.insert(info[1]);
        }

        int last = 0;
        for(int p: unique_points){
            int h = stree.query(indexes[p]);
            if(h != last)
                res.push_back(make_pair(p, h));
            last = h;
        }

        return res;
    }
};


int main() {

    int n = 5;
    int buildings[5][3] = {
            {2, 9, 10},
            {3, 7, 15},
            {5, 12, 12},
            {15, 20, 10},
            {19, 24, 8}
    };
    vector<vector<int>> vec;
    for(int i = 0 ; i < n ; i ++)
        vec.push_back(vector<int>(buildings[i], buildings[i] + 3));

    vector<pair<int, int>> res = Solution().getSkyline(vec);
    for(pair<int, int> p: res)
        cout << p.first << " " << p.second << endl;

    return 0;
}