백준 - 11000번 강의실 배정

문제

언제 시작해서 언제 끝나는 수업이 n개 주어지는데,
최소의 강의실을 사용해서 모든 수업을 가능하게 하려고 한다
최소 몇 개가 필요할까?

생각

모든 수업을 다 처리해줘야하니까,

맨 처음 시작하는 수업을 강의실 1곳에서 시작하고,

시작하는 시간 순으로 수업을 보면서,
비어있는 강의실이 있으면 그 수업을 하고,
비어있는 강의실이 없으면 강의실 개수를 추가하고 그곳에서 수업을 한다

강의실이 비어있어?

사용 중인 강의실에 끝나는 시간들을 저장해놓고, 정렬을 한다.
제일 빨리 끝나는 강의실의 시간을, 그 다음 수업의 시작하는 시간보다 빠르면
그곳은 비어있어서 수업을 할 수 있다고 보았다

왜 시작하는 시간 순으로?

회의실 배정 문제는 끝나는 시간 순으로 보면서 일정을 채웠다

이건 모든 회의를 다 하는게 아니라, 최대한 많은 회의를 선택하는거니까
빨리 끝나는 회의을 선택하면, 그 뒤에 더 많은 회의를 선택할 기회가 있다

근데, 이 문제는 모든 강의를 다 해줘야하고,
효율적으로 강의실을 써도, 모든 강의실이 다 비어있지 않은 경우엔
강의실의 수를 추가해주는 문제이기 때문에

시작하는 시간 순으로 강의 정보들을 보고, 가능하면 바로바로 수업하고,
비어있는 강의실이 없으면, 강의실을 추가하는 건 어쩔 수 없다.

굳이 비어있는 강의실이 있는데, 뒤에 다른 수업을 위해
이 수업을 처리하지 않는 것도 안 됌!
모든 수업 해야하니까

구현 방법

우선순위 큐를 사용해서 강의실들의 끝나는 시간을 저장했다

그리고 시작 시간 순으로 정렬된 수업 정보들을,
제일 빨리 끝나는 강의실의 종료 시간(q.top())과 비교한다

제일 빨리 끝나는 강의실의 종료 시간이, 현재 수업 시작 시간보다 늦으면
모든 강의실에서 수업을 할 수 없으므로, 강의실을 추가
(새로 끝나는 시간을 q에 추가) (경우 1)

아닌 경우에는 그 강의실에서 수업 가능!
q.top() 강의실 정보는 빼서 버리고, q에 새로운 정보 업데이트
(q.pop()하고, 새로 끝나는 시간을 q에 추가) (경우 2)

sort(info.begin(), info.end()); // 시작 시간 순으로 정보를 정렬

q.push(info[0].second); //제일 먼저 시작하는 수업을 1개의 강의실에서 함

for (int i = 1; i < n; i++) {
    if (q.top() > info[i].first) { //경우 (1)
        q.push(info[i].second);
    }else { //경우 (2)
    	q.pop();
        q.push(info[i].second);
    }
}

모든 수업을 보고 난 후, 큐의 사이즈가 총 필요한 강의실의 수이다
큐에 현재 사용한 강의실에서 끝나는 시간을 저장해놓은 것이기 때문에!!

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <functional>

using namespace std;

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

	int n, result = 0;
	vector<pair<int, int>> info;
	priority_queue<int, vector<int>, greater<int>> q; //시작 가능한 시간 넣어놔

	cin >> n;

	for (int i = 0; i < n; i++) {
		int startt, endt;
		cin >> startt >> endt;
		info.push_back(make_pair(startt, endt));
	}

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

	q.push(info[0].second);

	for (int i = 1; i < n; i++) {
		if (q.top() > info[i].first) {
			q.push(info[i].second);
		}else {
        	q.pop();
			q.push(info[i].second);
		}
	}

	cout << q.size();

	return 0;
}