[백준 1931] 회의실배정

https://acmicpc.net/problem/1931

---

해설

이 문제는 그리디 알고리즘을 생각해봐야 한다. 

 

문제 푼 방법

 

i) 끝나는 시간을 기준으로 정렬한다.

ii) 0번째 배열의 끝나는 시간을 finish에 저장한다.

iii) 1번 배열부터 for문을 돌려 finish 가 i의 시작하는 시간보다 작거나 같으면 cnt를 1 증가 시켜주고, finish에 i의 끝나는 시간을 저장해준다.

 

마지막에 cnt 를 출력해주면 된다.

 

 

˙˙˙

 

소스코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	vector<pair<int, int> >vp;
	int n; cin >> n;
	for(int i=0; i<n; i++){
		int a,b; cin >> a >> b;
		vp.push_back({b,a});
	}
	sort(vp.begin(), vp.end());
	int cnt=1;
	int finish = vp[0].first;
	for(int i=1; i<n; i++){
		if(vp[i].second >= finish){
			cnt++;
			finish = vp[i].first;
		}
	}
	cout << cnt << '\n';
}