문제

가장 먼저 시작하는 회의부터 선택 할 경우 아래와 같이 늦게 시작하는 회의가 더 짧을 수 있는 경우의 반례가 존재하므로 최적의 답을 구할 수 없다. 원래 탐욕법으로는 최적을 구하기 보다 최적에 가까운 답을 구하는게 보통이지만 이 문제는 최적의 답(또는 최적의 답 중 하나)을 구할 수 있기 때문에 이 방법을 사용하여 답을 구할 수 없다.

가장 짧은 회의부터 선택할 경우에는 아래와 같이 먼저 시작하고 회의 시간이 더 긴 회의를 시작할 경우 더 많은 회의를 선택할 수 있는 경우가 존재하기 때문에 최적의 답을 구할 수 없다.

코드 상에서 위 방법들에 대한 반례에 대해 처리한다고 해도 결국 다른 반례가 나오기 때문에 위 방법들로는 해결할 수가 없다.

이 문제를 해결하는 방법은 가장 빨리 끝나는 회의부터 선택하는 것인데 가장 빨리 끝나는 회의를 선택할수록 그 뒤에 선택할 수 있는 회의시간이 늘어나기 때문에 어떤 경우라도 가장 많이 선택할 수 있다.

코드는 아래와 같이 짰다. 회의의 시작시간과 종료 시간을 가지고 있는 meeting 구조체를 만들고(이 부분은 pair를 사용하여도 된다) 모든 회의를 종료 시간이 빠른 순(만약 종료 시간이 같다면 시작 시간이 빠른 순)으로 정렬한 다음 모든 회의를 확인하면서 선택할 수 있는 가장 빨리 끝나는 회의를 선택하게 하였다.

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

struct meeting{
	int start,end;
};

int cmp(const meeting &a, const meeting &b){
	if(a.end == b.end)
		return a.start < b.start;
	return a.end < b.end;
}

int main() {
	int n,i,s,e,last=-1,c=0;
	meeting t;
	vector<meeting> v;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d%d",&s,&e);
		t.start = s;
		t.end = e;
		v.push_back(t);
	}
	sort(v.begin(),v.end(),cmp);
	for(i=0;i<n;i++){
		if(v[i].start >= last){
			last = v[i].end;
			c++;
		}
	}
	printf("%d",c);
	return 0;
}