[백준 1931번][C++] 회의실 배정

그리디 알고리즘 이용 -> 끝나는 시간이 제일 작은 순으로 정렬하여 풀었습니다

 

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

//회의들을 <시작 시간, 끝나는 시간> 순으로 저장
vector<pair<int, int>> consel;

//끝나는 시간이 빠른 순으로 정렬하되 같으면 먼저 시작하는 순으로 정렬
bool cmp(pair<int, int> a, pair<int, int> b) {
	if (a.second == b.second)
		return a.first < b.first;
	else
		return a.second < b.second;
}

int main() {
	//최대 회의 수
	int conselNum = 0;

	//test 케이스
	int test;
	cin >> test;

	//회의 시간을 입력받아 저장
	for (int i = 0; i < test;i++) {
		int input1, input2;
		cin >> input1 >> input2;

		consel.push_back(make_pair(input1,input2));
	}

	//상기 설정한 순서대로 배열
	sort(consel.begin(), consel.end(), cmp);

	//계속 업데이트 해줄 끝나는 시간
	int endTime = -1;

	/*모든 배열을 돌며 끝나는 시간이 endTime보다 이후이면
	업데이트해주고 최대회의 수 증가*/
	for (int i = 0 ;  i <test ; i++) {
		if (endTime <= consel[i].first) {
			endTime = consel[i].second;
			conselNum++;
		}
	}

	cout << conselNum;
}