Given_N_buildings in a x-axis，each building is a rectangle and can be represented by a triple (start, end, height)，where start is the start position on x-axis, end is the end position on x-axis and height is the height of the building. Buildings may overlap if you see them from far away，find the outline of them。

An outline can be represented by a triple, (start, end, height), where start is the start position on x-axis of the outline, end is the end position on x-axis and height is the height of the outline.

Notice

Please merge the adjacent outlines if they have the same height and make sure different outlines cant overlap on x-axis.

Have you met this question in a real interview?

Yes

Example

Given 3 buildings：

[
  [1, 3, 3],
  [2, 4, 4],
  [5, 6, 1]
]

The outlines are：

[
  [1, 2, 3],
  [2, 4, 4],
  [5, 6, 1]
]

class Solution {

public:

/\*\*

 \* @param buildings: A list of lists of integers

 \* @return: Find the outline of those buildings

 \*/

vector<vector<int> > buildingOutline\(vector<vector<int> > &buildings\) {

    // write your code here

    vector<vector<int>> res;

    if \(buildings.empty\(\)\) {

        return res;

    }

    vector<Node> points;

    multiset<int> heap;

    for \(auto& building : buildings\) {

        points.push\_back\(Node\(building\[0\], building\[2\], 1\)\);

        points.push\_back\(Node\(building\[1\], building\[2\], 0\)\);

    }

    NodeCompare cmp;

    sort\(points.begin\(\), points.end\(\), cmp\);

    heap.insert\(0\);

    vector<pair<int, int>> outlinePoints;

    for \(auto point : points\) {

        if \(point.isLeft\) {

            if \(point.h > \*heap.rbegin\(\)\) {

                outlinePoints.push\_back\({point.x, point.h}\);

            }

            heap.insert\(point.h\);

        } else {

            heap.erase\(heap.find\(point.h\)\);

            if \(point.h > \*heap.rbegin\(\)\) {

                outlinePoints.push\_back\({point.x, \*heap.rbegin\(\)}\);

            }

        }

    }

    for \(int i = 0; i < outlinePoints.size\(\)-1; ++i\) {

        if \(outlinePoints\[i\].second > 0\) {

            res.push\_back\({outlinePoints\[i\].first, outlinePoints\[i+1\].first, outlinePoints\[i\].second}\);

        }

    }

    return res;

}

private:

struct Node {

    Node\(int \_x, int \_h, int \_isLeft\):x\(\_x\), h\(\_h\), isLeft\(\_isLeft\) {}

    int x, h, isLeft;

};

struct NodeCompare {

    bool operator\(\) \(const Node &lhs, const Node &rhs\) const {

        if \(lhs.x != rhs.x\) {

            return lhs.x < rhs.x;

        }

        if \(lhs.isLeft != rhs.isLeft\) {

            return lhs.isLeft > rhs.isLeft;

        }

        if \(lhs.isLeft\) {

            return lhs.h > rhs.h;    

        } else {

            return lhs.h < rhs.h;   

        }

    }  

};

};