백준 11000번 : 강의실 배정 C++

 

이게 골드라니?! 하는 문제였다.

골드가 다 이러면 얼마나 좋을까..

 

 

강의실을 넘겨받을수 있냐없냐 문제다.

1. 1~3시 강의실을 2~4강의가 넘겨받을수없으므로 새로운 강의실이 필요하다.
2. 3~5시 강의면 1~3시 강의실을 넘겨받을 수 있다.
3. pq의 기본 정렬은 내림차순이므로 강의실별 강의 끝나는 시간을 -를 붙여서 pq에 넣는다.
4. 만약 어떤 강의가 pq의 top에 있는 가장 빨리 끝나는 강의보다 시작시간이 같거나 늦으면 pop 하고 빠르면 pop하지 않는다.
5. 그리고 그 강의의 끝나는 시간을 pq에 넣는다.

 

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

using namespace std;
int n;
const int MAX = 200001;
pair<int, int> arr[MAX];
// 현재 가장 빨리 끝나는 강의의 T가 top에 오도록 담는 queue
priority_queue<int> pq;

int main(void) {

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i].first >> arr[i].second;
	}

	// 시작시간인 S의 오름차순 정렬
	sort(arr, arr + n);

	// pq는 기본이 내림차순이므로 오름차순되게 -붙임
	pq.push(-arr[0].second);

	for (int i = 1; i < n; i++) {
		// 현재 가장 빨리 끝나는 강의의 강의실을 쓸수 있는지 판단
		if ( -pq.top() <= arr[i].first) {
			// 현재 pq의 top인 강의실을 이어받을수 있으므로 top 을 pop
			pq.pop();
		}
		// 강의실을 이어받은 새로운 강의실을 쓰든 pq에 강의 끝나는 시간을 넣는다.
		pq.push(-arr[i].second);
	}

	cout << pq.size() << '\n';
}