BOJ (C/C++) 1931번: 회의실 배정

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

1931번: 회의실 배정

---

풀이

끝나는 시간이 먼저 오는 것을 기준으로, 끝나는 시간이 같다면 시작 시간이 빠른 걸 기준으로 정렬하였다.

시작 시간이 빠른 걸 기준으로 정렬해줘야 하는 이유

1 2

3 3

2 3

인 경우 정렬하면 1 2 -> 2 3 -> 3 3으로 3개의 회의를 할 수 있기에 끝나는 시간이 같은 경우 시작 시간이 이른 걸 먼저 정렬해야 함

정렬 후, 앞의 회의가 끝나는 시각 <=뒤 회의가 시작하는 시각이면 해당 회의를 선택하였다.

---

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

vector <pair<int, int>> V;

// 끝나는 시간이 먼저, 같은 경우 시작 시간이 앞선 것부터 정렬
bool cmp(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() {
	int N, s, e;

	// input
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &s, &e);
		V.push_back({ s,e });
	}

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

	// 회의 개수 카운트
	int cnt = 1, end;
	end = V[0].second;
	for (int i = 1; i < N; i++) {
		if (end <= V[i].first) {
			cnt++;
			end = V[i].second;
		}
	}

	printf("%d", cnt);
	return 0;
}