회의실 배정 (feat. 백준, 1931번)

회의실 배정
https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(const pair<int, int>& v1, const pair<int, int>& v2) {
	if (v1.second == v2.second)
		return v1.first < v2.first;
	return v1.second < v2.second;
}
int main() {
	register int N, tmp, answer = 1;
	vector<pair<int, int>> arr;
	cin >> N;
	for (register int i = 0, x, y; i < N; ++i)
		cin >> x >> y, arr.push_back(make_pair(x, y));
	sort(arr.begin(), arr.end(), cmp);
	tmp = arr[0].second;
	for (register int i = 1; i < N; ++i) {
		if (tmp <= arr[i].first) {
			++answer;
			tmp = arr[i].second;
		}
	}
	cout << answer;
	return 0;
}
// *&)*@*

1. 정렬만 잘하면 되는 문제입니다.
2. 종료 시간을 기준으로 sort를 취하고, 만약 종료 시간이 같다면 시작 시간으로 sort를 취하는 cmp를 정의합니다.
3. 이후 최초 0번째 시작-종료 시간 중 second를 기준으로 1번째부터 이전의 종료 시간과 시작 시간을 비교한 뒤, 만약 조건 (<=) 이 된다면 회의를 증가시켜주고 (++answer) 마지막 종료 시간을 갱신시켜줍니다.
4. 이후 2번째의 시작시간에 대해서 다시 반복해서 비교합니다.