[그리디 #18] BOJ 11000 - 강의실 배정

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

11000번: 강의실 배정

 

접근 방법

저번에 풀었던 최소 회의실 개수와 같은 문제이다.

 

https://parvegoongame.tistory.com/126

[그리디 #16] BOJ 19598 - 최소 회의실 개수

 

해당 알고리즘과 완전히 같다.

대략 설명하면 다음과 같다.

 

하나의 회의실에서 최대한 많은 회의를 연달아서 진행하는 것이 유리하다.

그러기 위해선, 회의가 끝나는 시간이 빠른 순서대로 해야한다.

 

회의 시간이 가장 적은 것을 골라야 하는가?

이에 대한 반례는 해당 포스팅을 참고하면 된다.

 

이 문제에서 현재 사용중인 회의실을 나타내기 위해 우선순위 큐를 사용하였다.

우선 순위 큐에 진행중인 회의실들의 끝나는 시간을 저장하여,  현재 시작하려는 회의의 시작시간보다 뒤면 새로운 회의실에서 회의가 진행되어야 한다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <cmath>

#define MAX 1010
#define INF 987654321

using namespace std;

int n;

vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> pq;

bool cmp(pair<int, int> a, pair<int, int> b) {
	if (a.second > b.second)
		return true;
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back(make_pair(a, b));
	}

	sort(v.begin(), v.end());
	
	int res = 0;
	for (int i = 0; i < n; i++) {
		pair<int, int> curr = v[i];
		int cnt = 0;

		while (!pq.empty() && pq.top() <= curr.first)
			pq.pop();

		pq.push(curr.second);
		cnt = (int)pq.size();

		res = max(cnt, res);
	}

	cout << res;
}