[BOJ] 1931번 회의실 배정(C++)

풀이 소요시간 : 20분

대표적인 그리디 스케쥴링 문제라고 한다. 이와 비슷한 문제들이 많이 떠돌아다니는 것을 보아, 접근 방식을 확실하게 공부하여 순차적 스케쥴링 문제에 잘 써먹어야겠다는 생각이 든다.

알고리즘의 확실한 이해를 위해 블로그에서 정보를 찾을 수 있었다.(출처 : https://cocoon1787.tistory.com/147) 위의 순차 그래프를 보아 회의가 끝나는 순으로 정렬하고, 그 다음 회의를 선정하면 최적의 회의 갯수를 얻을 수 있다는 것을 알 수 있다.

전체 코드

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

int N;
int Cnt = 0;


int main() {

	cin >> N;
	vector<pair<int, int>> Vector(N);
	for (int i = 0; i < N; i++) {
		cin >> Vector[i].second >> Vector[i].first;
		//first = 회의 종료 시간, second = 회의 시작 시간
	}

	sort(Vector.begin(), Vector.end());
	int Component = 0;
	for (int i = 0; i < N; i++) {
		if (Component <= Vector[i].second) {
			//회의가 빨리 끝나는 순에서 현재 시작이 가능한 회의
			Component = Vector[i].first;

			cout << Vector[i].second << ' ' << Vector[i].first << endl;
			Cnt++;
		}
	}
	cout << Cnt;
}