[BOJ] 백준 1931. 회의실 배정 (Silver II)

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

1931번: 회의실 배정

 

너무나도 유명한 문제이다.

아주 예전에 풀었었지만, 복습 겸 다시 한 번 풀어보았다.

굉장히 유명하기도 하고, 시리즈 문제도 매우 많은 편이다.

---

의식의 흐름 및 해설

회의를 최대한 많이 하기 위해서는, 

최대한 빈 회의시간이 없도록 해야 한다.

따라서 항상 최적해 풀이를 사용하는 그리디로 접근하면 될 듯하다.

 

그럼 이제 여기서 여러가지 생각이 들 것이다.

"회의 시간이 짧은 순으로 정렬해야되나?", "회의 시작 시각이 이른 순?", "회의 종료 시각이 빠른 순?"

정답은 바로 "회의 종료 시각이 빠른 순으로 정렬하되, 같을 경우 시작 시각이 이른 순으로 정렬"하면 된다.

 

시작 시각이 빠른 순으로 정렬할 경우,

시작 시각은 더 느리나, 끝나는 시각이 더 빠른 반례들을 놓치게 된다.

 

따라서 시작 시각은 별로 중요하지 않다. 

항상 끝나는 시각이 더 빠르게. 어차피 회의는 한 번이라도 더 많이 하면 이득이니까!

다만, 끝나는 시각이 동일한 회의는 시작 시각이 더 빠른 회의를 선택해야 한다.

아래와 같은 반례 때문이다. 이는, 시작 시각과 종료 시각이 같은 회의가 존재할 수 있기 때문이다.

2
1 2
2 2

 

그리디는 항상 최적의 경우를 생각하려면 어떻게 해야 할지, 그러한 반례들은 뭐가 있을지 꼼꼼하게 생각해보는 것이 중요한 듯하다. 이는 쉬운 문제일수록 당연하게 느껴지나, 어려운 문제일수록 반례를 생각해내기 어렵거나, 반례가 너무 많기 때문에 굉장히 어렵게 느껴진다.

 

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 100001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int N;
vector<pi> v;
bool cmp(pi p1, pi p2) {
	if (p1.second == p2.second)
		return p1.first < p2.first;
	return p1.second < p2.second;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	v.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i].first >> v[i].second;
	}
	sort(all(v), cmp);
	int t = v[0].second, ans = 1;
	for (int i = 1; i < N; i++) {
		if (v[i].first < t)
			continue;
		ans++;
		t = v[i].second;
	}
	cout << ans << "\n";
}