[Gold 5] 11000번 강의실 배정

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

11000번: 강의실 배정

 

이 문제는 그리디 알고리즘을 통해 해결할 수 있다.

입력은 벡터를 사용해서 S와 T를 pair형태로 삽입한다.

그 후 우선순위 큐를 greater로 정렬하고, vector의 두번째 값인 T를 큐에 삽입한다.

큐에 모든 vector의 second 값을 삽입하는데 이때 가장 작은 값이 현재 벡터의 S값보다 작거나 같으면 큐에서 값을 뺀다.

 

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

int N;
int main() {
	cin >> N;
	priority_queue<int, vector<int>, greater<int>> q;
	vector<pair<int,int>> v;
	for (int i = 0; i < N; i++) {
		int S, T;
		cin >> S >> T;
		v.push_back(make_pair(S, T));
	}
	// 1 3 3 5, 2 4, 6 7
	// 1 3 3 5  2 4 6 7
	// 13 3 5 6 7, 2 4

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

	q.push(v[0].second);
	for (int i = 1; i < N; i++) {
		q.push(v[i].second);
		if (q.top() <= v[i].first) {
			q.pop();
		}
	}
	cout << q.size() << '\n';
}