C++ / 백준 / 11000 / 강의실 배정

문제

 

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

11000번: 강의실 배정

문제풀이

 

우선순위 큐를 이용하면 간단하게 풀 수 있다.

먼저 강의 시간을 입력받는 벡터를 선언하고 우선순위 큐를 선언한다.

우선순위 큐는 먼저 끝나는 강의가 맨 앞에 들어가게끔 오름차순 정렬을 한다.

시간을 모두 입력받았으면, 입장시간 기준으로 오름차순 정렬한다.

 

반복문을 통해 모든 강의시간표를 확인한다.

우선순위 큐에는 진행중인 강의만 들어가있다.

 

우선순위 큐가 비어있으면 수업을 강의실을 하나 배정한다.

가장 먼저 끝나는 강의의 시간과 현재 배정할 강의의 입장 시간을 비교하고, 입장 시간이 더 빠른경우 push하여 강의실을 하나 더 배정한다.

모든 강의에 대해 반복한다.

 

answer는 매순간 answer와 우선순위 큐의 사이즈를 비교하여 큰 값을 저장한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

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

	int N(0), idx(0), answer(0), cnt(0);
	cin >> N;
	vector<pair<int, int>>course(N);
	priority_queue<int, vector<int>, greater<int>>pq;

	for (idx = 0; idx < N; ++idx) {
		cin >> course[idx].first >> course[idx].second;
	}

	sort(course.begin(), course.end());

	for (idx = 0; idx < N; ++idx) {
		while (!pq.empty() && course[idx].first >= pq.top()) {
			pq.pop();
		}
		if (pq.empty() || course[idx].first < pq.top()) {
			pq.push(course[idx].second);
		}
		cnt = pq.size();
		answer = max(answer, cnt);
	}
	cout << answer;
}