백준 1931번 : 회의실 배정

문제 접근

---

이전 회의 시간의 끝나는 시간보다 늦게 시작하는 회의 중, 가장 빨리 끝나는 회의만으로 구성하면 가장 많을 수 밖에 없다. 다른 회의들보다 빨리 끝난다는 건 그만큼 더 넣을 수 있다는 것이니 증명 끝! 예를 들어 1~5 보다 4~6이 효율적이려면 4 이하로 끝나는 회의가 있어야 되는데 그럼 애초에 4~6을 선택할 바에는 4 이하로 끝나는 회의를 선택하겠지? 4는 당연히 5보다 작고 ㅋㅋ 그럼 첫 줄의 가정은 성립한다는 걸 알 수 있다.

 

이전 회의의 끝나는 시간과 다음 회의의 시작하는 시간이 같아도 되는 걸 고려하지 않아서 한 번 틀렸었고, 정렬한 뒤 첫번째 pair 를 첫 회의로 잡았기 때문에 23행 for 문에서는 i=1 부터 시작해야되는데 0부터 시작해서 또 한 번 틀렸었다. 실수도 실력이당. 조심하자.

 

 

문제 코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	int N, start, end, ans=1, cur;
	vector<pair<int,int>> schedule;
	
	cin>>N;
	
	for(int i=0; i<N; ++i)
	{
		cin>>start>>end;
		schedule.push_back(make_pair(end,start));
	}
	
	sort(schedule.begin(), schedule.end());
	cur = schedule[0].first;
	
	for(int i=1; i<N; ++i)
		if(cur<=schedule[i].second)
		{
			cur = schedule[i].first;
			++ans;
		}
	
	cout<<ans<<'\n';
}