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

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

1931번: 회의실 배정

 

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

bool compare(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, a, b, t, cnt = 1;
	cin >> n;
	
	vector<pair<int, int>> v;
	
	for(int i = 0; i < n; i++){
		cin >> a >> b;
		v.push_back({a, b});
	}
	
	sort(v.begin(), v.end(), compare);
	
	t = v[0].second;
	for(int i = 1; i < n; i++){
		if(v[i].first < t) continue;
		t = v[i].second;
		cnt++;
	}
	
	cout << cnt << endl;
	return 0;
}

회의가 끝나는 시간을 오름차순으로, 끝나는 시간이 같다면 시작시간이 오름차순이 되도록 정렬한다.

첫 번째 회의가 끝나는 시간을 t로 놓고, 다음 회의가 시작하는 시간이 t보다 큰 경우에 카운트하고 회의가 끝나는 시간을 다시 t로 놓는 것을 반복한다.