Boj 1931) 회의실 배정

문제

백준 1931

설명

유명한 스케듈링 문제이다.

어딘거의 학습자료 에 간단한 증명이 있다. 간략하게 설명하면 어떤 부분 최적해에서 다음 스케듈을 추가한다고 하자. 부분 최적해에서 어떤 스케듈을 빼고 다음 스케듈을 넣는다면 잘해야 현상유지이고 아니면 갯수가 더 작아져 최적해가 될 수 없다, 그러면 부분 최적해를 건들지 않고 스케듈을 추가한다고 하자. 다음으로 빨리 끝나는 스케듈 \(j\) 가 있을 때, \(j\) 외의 스케듈 \(j'\) 를 추가하게 된다면 \(j'\) 빼고 \(j\) 넣어도 상관없고, 차지하는 범위가 더 줄어드니 \(j\) 를 넣는게 이득이다.

그러므로 가장 빨리 끝나는 순으로 추가하면 된다. 단, 끝나는 시간이 같으면 빨리 시작하는 순으로 넣어야한다.

시간 복잡도

O(\(\log{N}\))

코드

using ii = pair<int, int>;
ii cs[100001];

int main()
{
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> cs[i].second >> cs[i].first; // 도착이 앞에 오게 해서 기본정렬 사용

	sort(cs, cs + n);
	
	int last = cs[0].first, cnt = 1;
	for (int i = 1; i < n; i++)
	{
		if (cs[i].second >= last)
		{
			cnt++;
			last = cs[i].first;
		}
	}
	cout << cnt;
}