백준 1931번
회의실 배정
그리디 알고리즘을 통해서 해결하는 문제이다.
탐욕법은 매순간 최선의 선택을 통해서 답을 찾아내는 알고리즘이다.
이 문제에서는 정해진 계획 안에서 최대한 많은 회의를 진행시켜야 한다.
최대한 많은 회의를 진행하려면 회의 리스트를 살피면서 가능한 회의를 전부 포함하면 된다.
이 탐색에 그리디 알고리즘을 적용하려면 회의 리스트에 적절한 정렬 수행을 해야한다.
첫번째로 회의 리스트를 끝나는 시간이 이른 회의 순으로 정렬하고
두번째로 끝나는 시간이 동일하면 시작하는 시간이 이른 회의 순으로 정렬한다.
이렇게 리스트를 정렬하면
위에서부터 먼저 선택하여 가능한 회의를 전부 선택하면 최대 사용할 수 있는 회의의 개수를 구할 수 있다.
이게 가능한 이유는 끝나느 시간이 이를 수록 시작하는 시간이 이를 수 밖에 없고 그 중에서도 시작하는 시간이 이른걸 고를 수록 회의시간이 짧은 회의를 구하게 되는 것이다.
따라서 동일한 시간 내에 더 많은 회의를 선택할 수 있다.
소스 코드를 살펴보자.
파이썬에서는 sort 함수에 key 함수를 인자로 제공할 수 있다.
x[1](끝나는 시간)을 우선으로 정렬하고 그 다음
x[0](시작하는 시간)을 기준으로 정렬한다.
반복문 내부에 조건문은 가장 마지막으로 끝난 회의의 시간이 현재 고려중인 회의의 시작시간보다 늦다면 시작시간을 해당 회의를 포함하지 않기 위함이다.
Whiplash We Flash