백준 11000

백준 11000

이 문제는 회의실 배정 문제와 비슷한데, 그 문제에서는 하나의 회의실만을 정해두고 하나의 회의실에서 회의할 수 있는 최대의 회의 수를 구하는 것이라면 이 문제는 강의실의 개수와 상관없이 주어진 강의를 모두 할 수 있는 필요한 최소한의 강의실 수를 구하는 문제이다.

강의가 겹치지 않아야 강의실에 많은 강의를 배치하니 가장 늦게 끝난 강의를 기준으로 그 강의의 시작시간보다 다른 강의의 끝나는 시간이 커지면
다른 강의실을 배치하고 만약 작다면 그 강의실을 배치하면 된다.

강의가 끝나는 시간을 기준으로 내림차순해서 정렬하고 최대힙으로 구성된 우선순위 큐에 가장 늦게 끝나는 강의의 시작 시간을 넣는다. 우선순위 큐에 들어있는 원소들이 강의실의 개수이다. 그럼 우선순위 큐에 들어있는 top의 원소와 비교해 다음 강의와 겹치는지 안겹치는지 확인한다. 겹치면 시작하는 강의시간과 다음 강의의 시작시간을 push하고, 겹치지 않으면 한 강의실에서 진행됐다는 말이므로 그 강의 시작시간를 pop하고 그 다음 강의시간을 push한다. 이걸 모든 강의를 반복하면 for문 한번으로 구하고자 하는 최소 강의실의 개수를 구할 수 있다.

#include<bits/stdc++.h>
using namespace std;
int n; int chk[200001];
vector<pair<int, int>> v;
priority_queue<int> pq;
int main() {

	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;

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

	sort(v.begin(), v.end(), greater<>());

	pq.push(v[0].second);

	for (int i = 1; i < n; i++) {

		int x = v[i].first; 
		int y = v[i].second;

		int z = pq.top();
		pq.pop();

		if (x > z)	pq.push(z);
		pq.push(y);
	}
	cout << pq.size();
}

처음에 풀이법이 생각나지 않아 이중포문으로 진행했다가 시간초과가 나서, 다른 사람의 풀이를 참고했다. 우선순위 큐로 생각을 아예 못했다.. 똑똑한 사람들 많다.. 다음에 풀 때 우선순위 큐도 생각해보기!

아래에는 다른 사람 풀이 보다가 발견한 우선순위 큐를 이용하지 않고 푼 풀이이다. 처음에 입력 받을 때, 시작하는 시간과 0을 저장하고 끝나는 시간과 1을 저장해서 최대로 많이 겹치는 강의시간대를 구해 답을 구한 풀이다.
이 방법도 의외로 많이 쓰임

#include<bits/stdc++.h>
using namespace std;
int n; 
vector<pair<int, int>> v;
bool compare(pair<int, int>& a, pair<int, int>& b) {
	if (a.first == b.first) return a.second > b.second;
	else return a.first < b.first;
}
int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		v.push_back({ a,0 });
		v.push_back({ b,1 });
	}

	sort(v.begin(), v.end(),compare);

	int cnt = 0; int ans = 0;
	for (int i = 0; i < v.size(); i++) {
		int x = v[i].first;
		int y = v[i].second;

		if (y == 0) cnt++;
		else cnt--;

		ans = max(ans, cnt);
	}
	cout << ans;
}