[그리디]백준 1931 회의실배정 C++

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

1931번: 회의실 배정

 

동전문제와 함께 그리디알고리즘의 대표적인 문제! 문제 처음 풀 때 막 간트차트도 그리고 고민했는데 어렵게 생각하지 말고 쉽게 생각하면 금방 풀린다 

회의의 갯수가 최대가 되야 하므로 내가 접근한 방법은 회의 시간이 짧은 순서대로 회의를 배정하는 것 이다.

그러기위해 시작 시간과 끝나는 시간을 담은 벡터를 회의 시간이 짧은 순서대로 먼저 정렬 해주었다.

참고로, 이때 sort함수 사용했는데 비교 함수를 정의하여 vector의 second값을 기준으로 오름차순 정렬을 해주고 second값이 같을 경우 first기준으로 정렬 해주었다.

if (a.second == b.second) { 
		return a.first < b.first;	// first값 기준 내림차순 정렬
//		return a.first > b.first; 은 first값 기준 내림차순 정렬
	}
	else {
		return a.second < b.second;	// second값 기준 오름차순 정렬
//		return a.second > b.second; 은 second값 기준 내림차순 정렬			
	}

정렬된 상태이므로 가장 회의 시간이 짧은 값은 vec[0].second

이제 반복문 돌면서 nowTime 보다 시작시간이 작은 회의는 배정할 수 없다(당연히 회의가 끝나야 다음 회의가 시작할 수 있으니까!) 

반대로 nowTime 보다 크거나 같을경우 nowTime 값(회의의 끝나는 시간이라고 생각) 갱신하고 cnt를 올려주면된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
vector<pair<int, int>> vec;
int cnt = 1; 
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() {

	cin >> n;
	int a, b;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		vec.push_back({ a,b });
	}
	sort(vec.begin(), vec.end(), cmp);
	int nowTime = vec[0].second;
	for (int i = 1; i < n; i++) {
		if (vec[i].first < nowTime) {
			continue;
		}
		else {
			nowTime = vec[i].second;
			cnt++;
		}
	}
	cout << cnt << endl;


}