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

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

1931번: 회의실 배정

---

문제 풀이

 그리디 알고리즘의 원리인 "현재 가장 좋은 것 고르기"에 기반해서 생각하면 최대 개수는 다음 회의까지 공백이 가장 짧을 때이다.

구조체로 구현한 배열은 회의 시간의 시작과 종료시간을 저장한다. 

STL에서 지원하는 sort 함수를 활용해서 배열의 종료시간을 기준으로 내림차순으로 정렬한다.

내림차순으로 정렬하는 이유는 공백 시간을 종료 시간으로 따질 것이기 때문이다.

또한, 정렬되어있는 배열을 통해서 i번째 회의의 시작 시간이 이전 회의의 종료 시간보다 크거나 같을 때를 따지기 때문에 회의의 개수를 따지기 쉽다.

느낀 점

 그리디 알고리즘에서 가장 중요한 것은 어떤 것이 최선이 되는지 따지는 것 같다. 그리고 문제도 매우 다양한 것 같다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

typedef struct {
	int s;
	int f;
}Time;

int n, cnt = 0;
int finish = 0;
Time t[100001];

int compare(Time t1, Time t2) {
	if (t1.f == t2.f) return t1.s < t2.s;
	else return t1.f < t2.f;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> t[i].s >> t[i].f;
	}
	sort(begin(t), begin(t) + n, compare);
	for (int i = 0; i < n; i++) {
		if (t[i].s >= finish) {
			finish = t[i].f;
			cnt++;
		}
	}
	cout << cnt;
}