백준 1933 : 스카이라인 c++

https://www.acmicpc.net/problem/1933

1933번: 스카이라인

설명 : 스위핑 + 우선순위큐를 이용해 풀이
시작 지점을 기준으로 정렬 한 후 하나씩 건물을 세워가면서 비교
만약 시작지점과 끝지점이 같다면 높이가 큰 순으로 정렬한다.
건물을 세울 때 L을 기준으로 L보다 작은 R을 가진 건물들은 제외하면서 진행
우선순위 큐는 높이가 높은 순으로, 높이가 같다면 R이 큰 순으로 정렬한다.

 

틀린이유 : 시작 지점과 끝 지점이 같을 때 고려를 하지않음

 

#include<bits/stdc++.h>
#include<time.h>


#define MAX 1000000007
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

//int dx[8] = { 0, 0, 1, -1, 0, 0, -1, -1 };
//int dy[8] = { 1, -1, 0, 0, -1, -1, 0, 0 };

int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};
/*
int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };
*/
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }

pair<pll, ll> v[100001];
bool cmp(pair<pll,ll> a, pair<pll,ll> b) {
    if (a.first == b.first) {
        return a.second > b.second;
    }
    else return a.first < b.first;
}
int main() {
    init();
    ll n; cin >> n;
    priority_queue<pll> pq;
    for (int i = 0; i < n; i++) {
        cin >> v[i].first.first >> v[i].second >> v[i].first.second;
    }
    sort(v, v + n, cmp);
    pq.push({ 0,INF });
    for (int i = 0; i < n; i++) {
        //내려가는 거 체크
        ll mx = pq.top().first;
        ll idx = pq.top().second;
        while (idx < v[i].first.first) {
            if (idx >= pq.top().second) {
                pq.pop(); continue;
            }
            cout << idx << " " << pq.top().first << " ";
            idx = pq.top().second;
            mx = pq.top().first;
        }
        
        
        //올라가는거 체크
        if (pq.top().first < v[i].second) {
            cout << v[i].first.first << " " << v[i].second << " ";
        }
        pq.push({ v[i].second,v[i].first.second });
    }

    ll mx = pq.top().first;
    ll idx = pq.top().second;
    while (idx < INF) {
        if (idx >= pq.top().second) {
            pq.pop(); continue;
        }
        cout << idx << " " << pq.top().first << " ";
        idx = pq.top().second;
        mx = pq.top().first;
    }
    
}