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

🌽 문제

🥕 입출력

🥔 풀이

입력받은 회의 시간을 회의가 빨리 끝나는 순으로,
끝나는 시간이 같다면 시작 시간이 빠른 순으로 정렬한다.
이유는 아래와 같다.

예를 들어 (0, 1)과 (1, 1)이 있다고 하자.
(1, 1) 다음에 (0, 1) 회의를 진행할 수 없지만
(0, 1) 다음에 (1, 1) 회의는 진행할 수 있다.

정렬을 마치면 앞에서부터 돌면서
선택된 회의가 종료되는 동시에 시작하거나 그 이후에 시작하는 회의가 있다면
cnt를 더해주고 회의 종료 시간 또한 새롭게 선택된 회의의 종료 시간으로 갱신한다.

🥬 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

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

	int N;
	cin >> N;
	vector<pair<int, int>> v(N);
	for (int i = 0; i < N; i++) cin >> v[i].first >> v[i].second;
	sort(v.begin(), v.end(), cmp);

	int cnt = 1;
	int endTime = v[0].second;
	for (int i = 1; i < N; i++) {
		if (v[i].first < endTime) continue;
		cnt++;
		endTime = v[i].second;
	}
	cout << cnt;

	return 0;
}

🥜 채점