<p>A city&#39;s <strong>skyline</strong> is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return <em>the <strong>skyline</strong> formed by these buildings collectively</em>.</p>

<p>The geometric information of each building is given in the array <code>buildings</code> where <code>buildings[i] = [left<sub>i</sub>, right<sub>i</sub>, height<sub>i</sub>]</code>:</p>

<ul>
	<li><code>left<sub>i</sub></code> is the x coordinate of the left edge of the <code>i<sup>th</sup></code> building.</li>
	<li><code>right<sub>i</sub></code> is the x coordinate of the right edge of the <code>i<sup>th</sup></code> building.</li>
	<li><code>height<sub>i</sub></code> is the height of the <code>i<sup>th</sup></code> building.</li>
</ul>

<p>You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height <code>0</code>.</p>

<p>The <strong>skyline</strong> should be represented as a list of &quot;key points&quot; <strong>sorted by their x-coordinate</strong> in the form <code>[[x<sub>1</sub>,y<sub>1</sub>],[x<sub>2</sub>,y<sub>2</sub>],...]</code>. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate <code>0</code> and is used to mark the skyline&#39;s termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline&#39;s contour.</p>

<p><b>Note:</b> There must be no consecutive horizontal lines of equal height in the output skyline. For instance, <code>[...,[2 3],[4 5],[7 5],[11 5],[12 7],...]</code> is not acceptable; the three lines of height 5 should be merged into one in the final output as such: <code>[...,[2 3],[4 5],[12 7],...]</code></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/01/merged.jpg" style="width: 800px; height: 331px;" />
<pre>
<strong>Input:</strong> buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
<strong>Output:</strong> [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
<strong>Explanation:</strong>
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> buildings = [[0,2,3],[2,5,3]]
<strong>Output:</strong> [[0,3],[5,0]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= buildings.length &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= left<sub>i</sub> &lt; right<sub>i</sub> &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>1 &lt;= height<sub>i</sub> &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>buildings</code> is sorted by <code>left<sub>i</sub></code> in&nbsp;non-decreasing order.</li>
</ul>


class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& bud) {
        
        vector<int> lines, h;
        vector<vector<int>> info; // boundary, h, build idx

        for(int i=0; i<bud.size(); i++){
            info.push_back({bud[i][0], bud[i][2], i});
            info.push_back({bud[i][1], bud[i][2], i});
        }

        sort(info.begin(), info.end(), [](vector<int> a, vector<int> b){
            if(a[0]<b[0]) return true;
            else if(a[0]==b[0]){
                return a[2]>b[2];
            }
            return false;
        });

        priority_queue<int> live, past;
        int cur_h=0, last_h=0;
        vector<vector<int>> ans;
        unordered_set<int> us;
        map<int, int> keep;

        for(int i=0; i<info.size(); i++){

            if(!us.count(info[i][2])){
                live.emplace(info[i][1]);
                us.insert(info[i][2]);

                cur_h = live.top();
                if(cur_h!=last_h){
                    keep[info[i][0]] = max(keep[info[i][0]], cur_h);
                    // ans.push_back({info[i][0], cur_h});
                }
                last_h = cur_h;
                
            }
            else{
                past.emplace(info[i][1]);
                us.erase(info[i][2]);

                while(!live.empty() && !past.empty() && live.top() == past.top()){
                    live.pop();
                    past.pop();
                }

                if(live.empty() && past.empty()){
                    keep[info[i][0]] = 0;
                    // ans.push_back({info[i][0], 0});
                    last_h = 0;
                }
                else{
                    cur_h = live.top();
                    if(cur_h!=last_h){
                        keep[info[i][0]] = max(keep[info[i][0]], cur_h);
                        // ans.push_back({info[i][0], cur_h});
                    }
                    last_h = cur_h;
                }

            }

        }
        
        auto it=keep.begin();

        while(it!=keep.end()){
            ans.push_back({it->first, it->second});
            it++;
        }
        // ans.push_back({info[info.size()-1][0], 0});

        // while(!live.empty() && !past.empty()){
        //     cur_h = live.top();
        //     if(cur_h==last_h){
        //         live.pop();
        //         past.pop();
        //     }
        //     last_h = cur_h;

        //     if(live.empty() && past.empty()){
        //         ans.push_back({info[info.size()-1][0], 0});
        //     }
        // }
        return ans;
    }
};




// class Solution {
// public:
//     vector<vector<int>> getSkyline(vector<vector<int>>& bud) {
        
//         vector<int> left, right;
//         vector<int> h;
//         map<int,int> vld;
//         map<int,int> vld2;

//         for(int i=0; i<bud.size(); i++){

//             auto it = lower_bound(right.begin(), right.end(), bud[i][0]);
//             auto ht = lower_bound(h.begin(), h.end(), bud[i][2]);

//             if(ht==h.end() || it == right.end()){
//                 vld[bud[i][0]] = max(vld[bud[i][0]], bud[i][2]);
//             }
//             // else
//             right.insert(it, bud[i][1]);
//             h.insert(ht, bud[i][2]);

//         }

//         sort(bud.begin(), bud.end(), [](vector<int> a, vector<int> b){
//             return a[1]<b[1];
//         });

//         h.clear();
//         for(int i=bud.size()-1; i>=0; i--){

//             // while(!left.empty()){
//             //     if(right[0]<bud[i][0]){
//             //         right.erase(right.begin());
//             //     }
//             //     else{
//             //         break;
//             //     }
//             // }
//             auto it = lower_bound(left.begin(), left.end(), bud[i][1]);
//             auto ht = lower_bound(h.begin(), h.end(), bud[i][2]);
//             int h_val = 0;

//             if(left.empty()){
//                 vld2[bud[i][1]] = 0;
//             }
//             else if(ht!=h.end() && it != left.begin()){ // not highest && overlap
//                 h_val = 0;
//             }
//             else if(ht==h.end() && it != left.begin()){ //highest && overlap
//                 int idx = --ht - h.begin();
//                 vld2[bud[i][1]] = max(vld2[bud[i][1]], h[idx]);
//             }
//             else if(it == left.begin()){
//                 vld2[bud[i][1]] = 0;
//             }
//             left.insert(it, bud[i][0]);
//             h.insert(ht, bud[i][2]);

//         }

//         vector<vector<int>> ans;

//         auto v1=vld.begin();
//         auto v2 = vld2.begin();
//         while(v1!=vld.end() && v2!=vld2.end()){
//             if(v1->first<v2->first){
//                 ans.push_back({v1->first, v1->second});
//                 v1++;
//             }
//             else{
//                 ans.push_back({v2->first, v2->second});
//                 v2++;
//             }
//         }

//         while(v1!=vld.end()){
//             ans.push_back({v1->first, v1->second});
//             v1++;
//         }

//         while(v2!=vld2.end()){
//             ans.push_back({v2->first, v2->second});
//             v2++;
//         }

//         return ans;
//     }
// };
47763