class Solution {
    struct Building
    {
        int x1 = 0;
        int x2 = 0;
        int h = 0;
        
        Building()
        {}
        
        Building(const vector<int> &source)
            : x1(source[0]),
            x2(source[1]),
            h(source[2])
        {}
        
        static bool isAfter(const Building &b1, const Building &b2)
        {
            return b1.x2 < b2.x1;
        }
        
        static bool isIntersect(const Building &b1, const Building &b2)
        {
            if(b1.x2<b2.x1 || b2.x2<b1.x1)
                return false;
            if(b1.x1==b2.x2 || b1.x2==b2.x1)
                return false;
            return true;
        }
        
        static int merge(Building &b1, Building &b2, Building &extra)
        {
            if(b2.x2<b1.x1)
                swap(b1,b2);
            // Same height buildings. Just join
            if(b1.h == b2.h)
            {
                int x1 = min(b1.x1, b2.x1);
                int x2 = max(b1.x2, b2.x2);
                b1.x1 = x1;
                b1.x2 = x2;
                return 1;
            }
            // Two neighbours buildings with common middle wall. Do nothing
            if(b1.x2==b2.x1 || b2.x2==b1.x1)
                return 2;
            // Two equals walls
            if(b1.x1==b2.x1 && b2.x2==b1.x2)
            {
                if(b2.h>b1.h)
                    swap(b1, b2);
                return 1;
            }
            
            // one inside another
            if(b1.x1<b2.x1 && b2.x2<b1.x2)
            {
                // Tallest outside
                if(b1.h>b2.h)
                    return 1;
                // Tallest inside
                extra.x2 = b1.x2;
                b1.x2 = b2.x1;
                extra.x1 = b2.x2;
                extra.h = b1.h;
                return 3;
            }
            // Just overlapping
            // Common wall
            if(b1.x1==b2.x1 || b1.x2==b2.x2)
            {
                // Most wide to first position
                if(b1.x2-b1.x1 < b2.x2-b2.x1)
                    swap(b1,b2);
                if(b1.h>b2.h)
                     return 1;
                if(b1.x1==b2.x1)
                {
                    swap(b1, b2);
                    b2.x1 = b1.x2;
                }
                else
                {
                    b1.x2 = b2.x1;
                }
                return 2;
            }
            if(b1.h > b2.h)
            {
                b2.x1 = b1.x2;
            }
            else
            {
                b1.x2 = b2.x1;
            }
            return 2;
        }
    };
    
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {

        list<Building> line;
        auto it = buildings.begin();
        line.push_back(Building(*it));
        Building extra;
        for(++it; it!=buildings.end(); ++it)
        {
            auto itLine=prev(line.end());
            Building b2(*it);
            if(Building::isAfter(*itLine, b2))
            {
                line.push_back(b2);
            }
            else
            {
                while(itLine != line.begin())
                {
                    auto itPrev=prev(itLine);
                    if(Building::isAfter(*itPrev, b2))
                        break;
                    itLine = itPrev;
                }
                int n = Building::merge(*itLine, b2, extra);
                if(n<=2)
                {
                    auto itPrev=itLine;
                    ++itLine;
                    if(n==2)
                        itPrev=line.insert(itLine, b2);
                    while(itLine != line.end() && itLine != itPrev && Building::isIntersect(*itPrev, *itLine))
                    {
                        if(Building::merge(*itPrev, *itLine, extra) == 1)
                            itLine = line.erase(itLine);
                        else
                        {
                            ++itLine;
                            ++itPrev;
                        }
                    }
                }
                if(n==3)
                {
                    ++itLine;
                    line.insert(itLine, b2);
                    line.insert(itLine, extra);
                }
            }
        }
        
        int lastX=-1;
        vector<vector<int>> ret;
        for(const auto &b : line)
        {
            if(lastX>0 && b.x1!=lastX)
                ret.push_back({lastX, 0});
            ret.push_back({b.x1, b.h});
            lastX = b.x2;
        }
        ret.push_back({line.back().x2, 0});
        return ret;
    }
};