백준 - 회의실 배정 (1931) [C++]

 이 문제는 그리디를 이용해서 푸는 문제이다. 일단 완전 탐색을 이용하는 것은 입력이 10만이므로 불가능하다. 따라서 그리디를 사용해야 하는데, 여기서 중요한 것은 끝나는 시간에 대해 오름차순으로 정렬하고, 끝나는 시간이 같을 때 시작 시간에 대해 오름차순 정렬해야 한다는 것이다. 결국 얼마나 많이 회의실을 배정할 수 있냐이므로, 끝나는 시간이 일찍 끝날 수록 많은 배정이 가능하기 때문이다.

 

 

 

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

using namespace std;

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int N;

	vector<pair<int, int>> meetings;

	cin >> N;

	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		meetings.push_back({ a, b });
	}

	sort(meetings.begin(), meetings.end(), compare);

	int index = 0;
	int answer = 0;
	int last = -1;

	while (index < meetings.size()) {
		int start = meetings[index].first;
		int end = meetings[index].second;

		if (last <= start) {
			answer++;
			last = end;
		}
		index++;
	}

	cout << answer << '\n';

	return 0;
}