[BOJ][C++] 백준 19598번: 최소 회의실 개수 (Gold V)

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

 

문제

서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.

입력

첫째 줄에 배열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231−1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최소 회의실 개수를 출력한다.

 

풀이

일단 시작시간과 끝나는 시간에 해당하는 숫자가 크기 때문에 long long 타입을 써야하는 점을 명심하자

 

이 문제의 풀이를 이해하고싶다면 그냥 직관적으로 생각하는게 제일 편하다

1. 회의를 배정하고 끝나는 시간을 회의실에 표시한다

2. 다음 회의의 시작 시간을 회의실들에 표시된 끝나는 시간과 비교한다

 

3. 시작 시간 >= 끝나는 시간 인 경우가 있으면 그 회의실에 배정, 없으면 새 회의실에 배정

회의들을 탐색하면서 반복

 

이때 회의를 탐색할때는 시작시간이 빠른 회의부터 배정해야한다.

입력으로 받은 회의 시간을 정렬하고 시작하자

 

이제 본격적으로 회의실에 배정을 할거다.

임의의 회의실 배열을 만들고 각 회의실의 회의가 끝나는 시간을 넣는 형태로 구현한다.

(회의실에 배정된 회의가 끝나는 시간을 명시하는 것과 동일)

 

이때 위에서 2번 단계를 할 때 <배정된 회의실 중 끝나는 시간이 가장 빠른 회의실> 하나와 비교하면 된다

매번 가장 시간이 빠른걸 순회하며 돌기엔 시간이 부족하니 priority_queue 를 이용했다.

우선순위 큐를 이용하면 pq.top()이 끝나는시간이가장빠른회의실의끝나는시간. 이다

 

회의들을 차례대로 보면서

회의실에 회의가 들어갈 수 있으면 (pq.top() <= 현재회의의 시작시간)

그 회의실에 회의를 넣고 (회의를 빼고, 현재 회의를 넣음 = pq.top(); pq.push(현재회의끝나는시간))

들어갈 수 없으면 새로운 회의실에 배정한다 (그냥 새로 값 넣음 = pq.push(현재회의끝나는시간))

 

// 풀이 : https://whkakrkr.tistory.com

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ci;

bool cmp(ci a, ci b) {
    return a.first < b.first;
}

int solution(int &n, vector<ci> &v) {
    int ans;
    
    sort(v.begin(), v.end(), cmp);
    
    priority_queue<ll, vector<ll>, greater<>>pq;
    pq.push(v[0].second);
    
    for(int i=1; i<n; i++) {
        ci cur = v[i];
        if(pq.top() <= cur.first) {
            pq.pop();
        }
        pq.push(cur.second);
    }
    
    ans = pq.size();
    
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	vector<ci>v(n);
	ll a,b;
	for(int i=0; i<n; i++) {
	    cin >> a >> b;
	    v[i] = {a,b};
	}
	
	cout << solution(n,v);
	
    return 0;
}