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

문제 링크: https://www.acmicpc.net/problem/1931

 

유명한 문제입니다. Activity Selection Problem이라고도 하는데요, 유명한(well-known) 그리디 문제입니다. 알고리즘 초보인 제가 알 정도면 거의 다 알고 있다고 봐도 무방합니다. 코드포스같은데는 나올 수가 없겠죠?

그리디로 푸는 건 알겠는데, 그리디로 어떻게 풀어야 할까요? 그리디 문제는 이 점이 어렵습니다. 어떤식으로 그리디로 풀어야할지 잘 생각해봐야 합니다.

• 회의실을 짧게 쓰는 순서대로 정렬한다: X
  반례: [4, 5]와 [1, 4], [5, 10]의 경우
• 먼저 시작하는 순으로 정렬한다: X
  반례: [0, 10]과 [1,2], [2, 3], [3, 4], ...

정답은 '회의 종료 시간 기준 오름차순 정렬'입니다. 이렇게 정렬한 뒤, 가장 일찍 끝나는 회의(S_min)를 선택한 뒤 순서대로 체크하면서 현재 회의와 겹치는 회의는 빼고, 겹치지 않으면 회의에 넣습니다. iteration이 끝나면 회의가 몇 개 있는지 출력합니다. 정렬 + 스위핑이라고 봐도 되겠네요.

증명은 다음과 같습니다. 회의 목록 S의 최적해 중 S_min을 포함하지 않는 답이 있다고 가정해보겠습니다. 이 목록에서 첫 번째로 열리는 회의를 지운 뒤 S_min을 추가하면 이것도 역시 최적해가 됩니다. 따라서 항상 S_min을 포함하는 최적해가 존재하게 됩니다.

 

그리디에 관한 내용은 나중에 게시물로 정리해 올려보겠습니다.

 

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
#include <bits/stdc++.h>
using namespace std;


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	
	int n;
	cin >> n;

	vector<pair<int, int>> vp(n);
	for (auto& [from, to] : vp)
		cin >> from >> to;

	
	// 끝나는 시간 순서 기준 오름차순 정렬
	sort(vp.begin(), vp.end(), [](auto& p1, auto& p2) {
		if (p1.second == p2.second)
			return p1.first < p2.first;
		return p1.second < p2.second;
	});


	int counter = 1;
	pair<int, int> rent = vp[0];	// from, to
	
	for (int i = 1; i < n; ++i) {
		if (vp[i].first < rent.second) {	//겹침
			continue;
		}
		else {
			rent = vp[i];
			++counter;
		}
	}

	cout << counter << '\n';

	return 0;
}