[SWEA] 4408 자기 방으로 돌아가기

 

그리디로 풀 수 있는문제라고 해야할까?!

 

서로 겹치는 부분이 있다면 방에 갈 수 없다

 

문제를 풀기 위해서는 뒤부터 보자!

나는 pq를 사용했다

 

내가 더 뒤에있는 사람부터 보면서 구간을 [a,b]라고해보자

그럼 나의 뒤에있는 사람은 [a`,b`]라고 할 때

 

1) 갈 수 있는경우 a`<b

이 때는 다시 a`값을 가지고 그 다음 친구를 보면된다!

 

2) 갈 수 없는경우 a`>b

이 때는 구간이 겹친다 따라서 a`를 저장해뒀다가 다시 pq에 넣어두자

 

소스코드

#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
int n, t;
 
int main() {
    scanf(" %d", &t);
    for (int tc = 1; tc <= t; tc++) {
        scanf(" %d", &n);
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < n; i++) {
            int x, y; scanf(" %d %d", &x, &y);
            int a = max(x, y); int b = min(x, y);
            pq.push({ (a+1)/2,(b+1)/2 });
        }
 
        int ans = 0;
        for (int a = 1; a <= 444 && !pq.empty(); a++) {
            int s = pq.size();
            int prev = 1e9;
            vector<pair<int, int>> vt;
            for (int i = 0; i < s; i++) {
                pair<int, int> p = pq.top(); pq.pop();
                if (p.first < prev) prev = p.second;
                else vt.push_back(p);
            }
            for (int i = 0; i < vt.size(); i++) pq.push(vt[i]);
            ans = a;
        }
        printf("#%d %d\n", tc, ans);
    }
}