백준 1931 - 회의실 배정

🔐 백준 1931 - 회의실 배정

https://www.acmicpc.net/problem/1931

🔑 풀이

우선 모든 경우의 수를 다 계산한다면 한 회의를 포함할지 말지로 나뉘므로 $ 2^N $ 시간이

걸릴 것이다. 하지만, 회의의 수가 100,000까지이므로, 이 풀이는 적절하지 않다.

이 문제는 그리디 알고리즘 중 Interval scheduling 문제에 해당한다.

Interval scheduling의 풀이 방법은 종료 시간에 따라 오름차순으로 정렬한 후,

제일 빨리 끝나는 것을 선택하는 방법이다. 이 방법을 선택하면 각 선택 단계에서 최선의

선택을 보장받을 수 있다.

🧩 코드