[백준] 1931 회의실 배정

[백준] 1931 회의실 배정

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

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

bool cmp(pair<int, int> a, pair<int, int> b) {
	//회의 끝나는 시간 빠른 순으로 정렬
	if(a.second < b.second) return true;
	//회의 끝나는 시간 같은 경우
	//회의 시작하는 시간 빠른 순으로 정렬
	if (a.second == b.second) return a.first < b.first;

	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n;
	cin >> n;

	vector<pair<int, int>> meeting;
	for (int i = 0; i < n; ++i) {
		int start, end;
		cin >> start >> end;
		meeting.push_back({ start, end });
	}
	sort(meeting.begin(), meeting.end(), cmp);

	int cnt = 0;
	int meetingEnd = 0;
	for (int i = 0; i < n; ++i) {
		if (meetingEnd <= meeting[i].first) {
			cnt++;
			meetingEnd = meeting[i].second;
		}
	}
	cout << cnt;
	return 0;
}

📌참고자료

• 반례
  https://www.acmicpc.net/board/view/95830

만약에 정렬이 시작시간에 전혀 관계없이, 종료시간으로만 정렬되게 된다면 문제가 생기게 됩니다.
1 3
8 8
4 8
이라는 예시에 대해서, 위와 같이 정렬될 수 있습니다.
그럴 때, 1 3과 8 8만 세므로 2가 나와서 오답이 됩니다.
실제로는 1~3시 1번, 4~8시 2번, 8~8시 3번으로 총 3개가 나와야합니다