백준 11000 강의실 배정 C++

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

11000번: 강의실 배정

뭔가 쉬울 거 같으면서도 될 거 같은 경우가 많았던 문제입니다. 저는 우선순위 큐를 이용해 풀었습니다.

 

먼저 각 입력으로 들어오는 값들을 정렬하고 (20만 개니까 n log n 인 걸로) 정렬 시 시작 시간이 빠른 순으로 정렬합니다.

그리고 우선순위 큐는 오름차순으로 세팅합니다.

 

우선순위 큐에 들어 가는 값은 각 수업이 끝나는 시간입니다.

이렇게 하는 이유는 우선 순위 큐의 top 값이 결국 가장 빨리 끝나는 시간을 의미하며, 시작 시간이 빠른 순으로 정렬한 수업들은 해당 top 값보다 빠른 시간이면 새로운 강의실이 필요한 것이며, 그렇지 않다면 해당 강의실을 쓰면 됩니다.

그러므로 새 수업의 시작 시간이 top 값보다 크거나 같은 경우 해당 원소를 pop 하고 새로운 수업의 끝나는 시간을 push 하면 됩니다.

 

우선순위 큐의 push, pop 복잡도는 log n 이므로 정렬을 포함하더라도 n log n 정도이므로 통과합니다.

 

코드는 다음과 같습니다.

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

using namespace std;

int n, s, t;
vector<pair<int, int>>vec; // {시작 시간, 끝 시간}
int res;

void init()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s >> t;
		vec.push_back({ s, t });
	}
	res = 0;
}

void sorting()
{
	sort(vec.begin(), vec.end()); // 시작 시간 빠른 순, 끝 시간 빠른 순
}

void result()
{
	priority_queue<int, vector<int>, greater<int>> pq;
	// 우선 순위 큐에 끝나는 시간 빠른 순으로 넣음
	// 그럼 시작 시간 빠른 순으로 입력 들어오면서 
	// 우선순위 큐의 top 원소인 끝나는 시간보다 빠르면
	// 새로운 원소로(끝나는 시간을), 
	// 느리거나 같으면 
	// 그 수업 끝나고 이어서 할 수 있는 거니 pop 하고 
	// 새로운 원소로(끝나는 시간을)

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

	for (int i = 1; i < n; i++) {
		int end_time = pq.top();
		int new_start_time = vec[i].first;
		int new_end_time = vec[i].second;
		if (end_time > new_start_time) {
			// 들어갈 수업 없음
			pq.push(new_end_time);
		}
		else {
			// 들어갈 수업 있음
			pq.pop();
			pq.push(new_end_time);
		}
	}

	res = pq.size();
}

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

	init();
	sorting();
	result();
	cout << res;
}