[백준 알고리즘] 11000 C++ 강의실 배정

 

• 그리디하게 풀어야 하지만 시간초과에 유의해야함
• 자료구조의 선택이 중요 => 우선순위 큐 사용
• 강의가 가장 일찍 끝나는 시간이 큐의 앞에 있으므로, 앞으로의 입력값은 강의 시작 시간이 전의 값들보다 같거나 앞서야함 ! 

이 두점을 유의해서 풀게 되면, 우선순위 큐 자료구조를 사용하고 std sort를 활용하여 pair 값( 강의실 시간 쌍 )을 정렬해주면 해결 할 수 있다.

 

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

std::pair<int, int> u[200001] = {};
int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n;
	std::cin >> n;

	int a, b;

	std::priority_queue<int, std::vector<int>, std::greater<int>> q;
	for (int i{ 0 }; i < n; i++) {
		std::cin >> a >> b;
		u[i].first = a;
		u[i].second = b;
	}

	std::sort(u, u + n);

	for (int i{ 0 };i<n;i++) {
		a = u[i].first;
		b = u[i].second;

		if (q.empty()) {
			q.push(b);
		}
		else if (q.top() <= a) {
			q.pop();
			q.push(b);
		}
		else q.push(b);
	}

	std::cout << q.size() << "\n";
}