[TIOJ]1202. 重疊的天際線

題目連結：http://tioj.ck.tp.edu.tw/problems/1202

可以用Heap維護～
當時間點到達房子的左界就push進去，超過右界就pop出來。

#include <bits/stdc++.h>
#define PB push_back
#define F first
#define S second
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
using namespace std;
typedef pair<int,int> Pair;
priority_queue<Pair , vector<Pair> ,less<Pair> > pq;
vector<int> v,g;
struct Ken{
    int l,h,r;
    bool operator < (const Ken &x)const{
        return l < x.l;
    }
}a[30004];
int main(){jizz
    int n,t;
    while(cin >> n ,n){
        v.clear();
        g.clear();
        t = 0;
        while(!pq.empty())pq.pop();
        pq.push({0,2147483647});
        for(int i = 0 ; i < n ; i++){
            cin >> a[i].l >> a[i].h >> a[i].r;
            g.PB(a[i].l),g.PB(a[i].r);
        }sort(a,a+n);sort(g.begin(),g.end());
        for(int i : g){
            while(t < n &&a[t].l == i)pq.push({a[t].h,a[t].r}),t++;
            while(pq.top().S <= i)pq.pop();
            if(v.empty() || pq.top().F != v.back())v.PB(i),v.PB(pq.top().F);
        }
        for(int i = 0 ; i < v.size() ; i++)
            cout << v[i] << " \n"[i == v.size()-1];
    }
    return 0;
}