[백준/BOJ] 1931번 회의실 배정 (C++)

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

1931번: 회의실 배정

문제 해결의 아이디어는 가장 끝나는 시간이 작은 회의실을 시작으로, 가능한 한 끝나는 시간 작은 회의실을 계속 고르면 되는 문제이다. 따라서 입력을 끝나는 시간을 기준으로 오름차순 정렬한다. (끝나는 시간이 혹시 같다면 시작 시간을 기준으로 오름차순) 그리고 반목문을 통해 현재 선택한 회의실의 끝나는 시간과 다음 회의실의 시작시간을 비교해가며 회의실을 선택하면 된다.

 

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

int 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(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, answer = 1;
	cin >> n;
	vector<pair<int, int> > v;
	for(int i = 0; i < n; i++) {
		int s, e;
		cin >> s >> e;
		v.push_back({ s, e });
	}
	sort(v.begin(), v.end(), cmp);
	for(int i = 0; i < n - 1; i++) {
		int j = i + 1;
		while(1) {
			if(v[i].second <= v[j].first) {
				i = j - 1;
				answer++;
				break;
			}
			j++;
			if(j == n) {
				i = j - 1;
				break;
			}
		}
	}
	cout << answer;
}