백준 11000 강의실 배정 풀이

사용언어

Visual studio 2019 C++

생각하기

우선순위 큐를 사용해서 풀어보자

우선순위 큐란 수를 여러개 넣어도 큰수를 앞으로 빼는 걸 말함!

쉽게 이해하려면.. 직접 넣어봐야된다

#include <iostream>
#include <queue>
using namespace std;

int main() {
	priority_queue<int> pq;
	pq.push(5);
	pq.push(3);
	pq.push(7);
	pq.push(1);

	cout << pq.top() << " ";
	pq.pop();
	cout << pq.top() << " ";
	pq.pop();
	cout << pq.top() << " ";
	pq.pop();
	cout << pq.top() << " ";
	pq.pop();
}

출력: 7 5 3 1

반례라기보단.. 거꾸로 있는 것도 생각해야 함!
3
19 20
12 19
1 12

[11000 풀이]

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

#define endl "\n"
using namespace std;

int n;
pair<int, int> p[200001];
priority_queue<int> pq;

int main() {
	cin >> n;

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

	pq.push(-p[0].second); 
	for (int i = 1; i < n; ++i) {
		if (-pq.top() <= p[i].first) {
			pq.pop();
			pq.push(-p[i].second);
		}
		else {
			pq.push(-p[i].second);
		}
	}

	cout << pq.size() << endl;
}