[백준 1374번] 강의실

www.acmicpc.net/problem/1374

1374번: 강의실

N개의 [강의 번호, 강의 시작시간, 강의 종료시간]이 있을 때,

강의 시간이 겹치지 않고 배정하기 위해 필요한 최소한의 강의실 개수를 구하라

 

이는 이미 시작한 강의의 종료시간이 새로 시작할 강의의 시작시간보다 작으면 강의실의 낭비를 줄일 수 있다.

 

먼저 강의 목록 중 시작시간과 종료시간을 입력받아 오름차순으로 정렬한다.

	//typedef pair<int, int> pii;
    
    for (int i = 0; i < n; i++) {
		int n, s, e;
		cin >> n >> s >> e;
		lec.push_back(pii(s, e)); 
	}

	sort(lec.begin(), lec.end()); //시작시간이 빠른것부터 시작

강의 시간 정렬

강의 목록을 처음부터 확인하며 강의 종료 시간을 오름차순 우선순위 큐에 넣는다.

--> 우선순위 큐는 진행되고 있는 강의의 종료 시간을 가지고 있다.

이는 우선순위 큐 속의 인자 수가 강의를 진행하기 위해 필요한 강의실의 수와 같다는 것을 알 수 있다.

 

이때, 새로운 강의의 시작시간이 큐 속의 시간보다 같거나 크다면 진행되고 있던 강의가 종료되었다는 것을 의미한다.

그러므로 큐 속에서 해당 종료 시간을 삭제하고 새로운 강의의 종료시간을 추가한다.

	//priority_queue <int, vector<int>, greater<int>> pq;//강의 종료시간
    
    int ans = 0;

	for (int i = 0; i < n; i++) {
		//새로운 강의의 시작시간이 진행중인 강의의 종료시간과 같거나 크면
		while (!pq.empty() && pq.top() <= lec[i].first) {
			pq.pop();
		}
		pq.push(lec[i].second);//강의의 종료시간
		int size = pq.size();//필요한 강의실의 수
		ans = max(ans, size);
	}

 

전체 코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

int n;
vector<pii> lec;//강의
priority_queue <int, vector<int>, greater<int>> pq;//강의 종료시간

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int n, s, e;
		cin >> n >> s >> e;
		lec.push_back(pii(s, e));
	}

	sort(lec.begin(), lec.end());//시작시간이 빠른것부터 시작

	int ans = 0;

	for (int i = 0; i < n; i++) {
		//새로운 강의의 시작시간이 진행중인 강의의 종료시간과 같거나 크면
		while (!pq.empty() && pq.top() <= lec[i].first) {
			pq.pop();
		}
		pq.push(lec[i].second);//강의의 종료시간
		int size = pq.size();//필요한 강의실의 수
		ans = max(ans, size);
	}

	cout << ans << "\n";
	return 0;
}