백준 1931번: 회의실배정

[문제 링크]

1931번: 회의실배정

---

알고리즘 문제 해결 전략에서도 풀어봤던 유형의 그리디 알고리즘 문제였지만 새로운 것을 알게된 문제였다.

 

회의가 빨리 끝나는 순으로 회의를 진행하면 항상 최적해를 얻을 수 있기 때문에 회의가 끝나는 시간을 기준으로 오름차순 정렬하여 회의를 진행하면 쉽게 정답을 얻을 수 있다.

 

필자는 STL algorithm 해더파일에 정의된 sort함수를 쓰지 않고 직접 퀵정렬을 구현해서 써봤는데 시간초과가 발생하였다.

문제에서 N이 최대 100,000이고 퀵정렬 최악의 시간복잡도가 O(N^2) 인 것을 고려하면 시간 초과가 뜨는 것이 이해는 갔지만 STL의 sort함수도 퀵정렬을 기반으로 동작한다고 알고 있었기 때문에 의구심이 들었다.

 

찾아본 결과 STL의 sort함수는 최악의 시간복잡도가 O(N^2)인 것을 보완한 특별한 정렬법을 사용한다고 한다.

 

https://www.acmicpc.net/board/view/16770

 

---

#include <iostream>
#include <algorithm>
using namespace std;

pair<int, int> schedule[100000];

int Greedy(int N)
{
	sort(schedule, schedule + N);

	int start = 0, ret = 0;

	for (int i = 0; i < N; i++)
	{
		if (start <= schedule[i].second)
		{
			ret++;
			start = schedule[i].first;
		}
	}

	return ret;
}

int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> schedule[i].second >> schedule[i].first;

	cout << Greedy(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 110 day