[백준 1931] 회의실 배정 - Greedy Algorithm

Introduction to Algorithm에도 나와있는 예제입니다. 위 문제는 한 가지 규칙을 정해서 Greedy하게 풀 수 있습니다. 

 

다음과 같은 예시에서 직관적으로, 일찍 끝나는 회의를 결정하면 최대한 많은 회의를 할 수 있음을 알 수 있습니다.

 

노란색 막대 4개를 선택할 수도 있으며, 초록색을 대신해서 선택할 수도 있습니다. 결과는 동일합니다.

 

즉 이 문제는 Greedy하게, 회의가 끝나는 시간이 이른 순으로 선택하면 답을 얻을 수 있습니다.

 

전체 코드는 다음과 같습니다.

 

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#pragma warning(disable:4996)

bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
	if (a.second == b.second)
		return a.first < b.first;
	return a.second < b.second;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int N, n1, n2;
	cin >> N;

	vector<pair<int, int>> v;
	for (int i = 0; i < N; i++) {
		cin >> n1 >> n2;
		v.push_back(make_pair(n1, n2));
	}

	sort(v.begin(), v.end(), cmp);

	int cnt = 1;
	int min = v[0].second;

	for (int i = 1; i < N; i++) {
		if (v[i].first >= min) {
			min = v[i].second; // 미리 정렬 해놓아서 사용할 수 있음
			cnt++;
		}
	}
	
	cout << cnt << '\n';

	return 0;
}