회사에 회의실이 하나밖에 없는데, n개의 팀이 각각 회의하고 싶은 시간을 제출했다고 하자. 이 중 서로 겹치지 않는 회의들만을 골라내서 진행한다고 했을 때 최대 몇 개나 선택할 수 있을 것인가?

해결법 : 가장 먼저 끝나는 회의를 선택하고, 이 회의와 겹치는 것들을 모두 지운 뒤 다시 이 중에서 가장 먼저 끝나는 회의를 선택하기를 반복하는 것.

1. 목록 S에 남은 회의 중 가장 일찍 끝나는 회의를 선택한다.
2. 이 회의와 겹치는 회의를 S에서 모두 지운다.
3. S가 텅 빌 때까지 반복한다.

정당성의 증명

• 탐욕적 선택 속성 : 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있는가 (가장 종료 시간이 빠른 회의를 포함하는 최적해가 반드시 존재하는가? → 가장 종료 시간이 빠른 회의를 포함하지 않는 답이 있다고 가정했을 때 가장 첫 회의 대신 가장 종료 시간이 빠른 회의를 포함하는 것도 해가 된다.)
• 최적 부분 구조 : 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있는가?

// 각 회의는 [begin, end) 구간 동안 회의실을 사용한다.
int n;
int begin[100], end[100];
int schedule()
{
	// 일찍 끝나는 순서대로 정렬한다.
	vector<pair<int,int>> order;
	for(int i = 0 ; i < n; ++i)
	{
		order.push_back(make_pair(end[i], begin[i]));
	}
	sort(order.begin(), order.end());
	// earliest : 다음 회의가 시작할 수 있는 가장 빠른 시간
	// selected : 지금까지 선택한 회의의 수
	int earliest = 0, selected = 0;
	for (int i = 0; i < order.size(); ++i)
	{
		int meetingBegin = order[i].second, meetingEnd = order[i].first;
		
		if(earliest <= meetingBegin)
		{
			earliest = meetingEnd;
			++selected;
		}
	}
	return selected;
}	

이를 동적계획법으로도 풀 수 있다. 각 단계에서의 해가 정해지고 변하지 않기 때문이다.