1931번 회의실배정(그리디) - ☆

#문제링크 : https://www.acmicpc.net/problem/1931

<전략>

1. 가장 먼저 시작하는 회의, 가장 짧게 진행하는 회의, 가장 빨리 끝나는 회의 등 총 3가지의 경우를 생각했다.

2. 우선 이중에서 가장 먼저 시작하는 회의를 고를 경우에는 반례가 생길 수 밖에 없다. 가장 먼저 진행하는 회의가 가장 길게 진행될 경우 중간의 회의들을 모두 놓치기 때문이다.

3. 가장 짧게 진행하는 회의 순으로 갯수를 셀 경우에도 반례가 생긴다. 예를들어, 1~4, 4~8, 3~5 의 시간동안 진행되는 회의가 있다고 하면, 답은 1~4, 4~8 로 최대 2번의 회의를 진행할 수 있지만, 가장 짧게 진행하는 회의가 3~5 이므로 이를 선택할 경우, 최대 1번의 회의밖에 진행할 수 없게 된다.

4. 결국, 가장 빨리 끝나는 회의를 먼저 담고, 그 이후에 시작하는 회의를 고르는 형식으로 풀면 된다. 여기서 중요한 점은 가장 먼저 끝나는 회의순으로 정렬한 뒤, 만약, 회의가 끝나는 시간이 동일하다면 이때에는 회의 시작시간이 빠른 순으로 정렬을 해야 한다는 점이다. 이렇게 정렬을 마치면, 8~8, 7~8 인 회의가 존재할 경우 7~8인 회의가 8~8인 회의보다 앞에 위치하므로 갯수를 세어줄 수 있기 때문이다.

※주의사항

1. 정렬을 마친 뒤, 탐색을 할 때, 지금 진행하는 회의의 종료시간보다 같거나 큰 시작시간을 가진 회의를 찾는 과정에서 해당 회의를 찾게 되면, 해당 회의의 인덱스만큼 반복자가 건너뛰어야 한다. 새로 지정된 회의시간을 현재 회의로 간주할 것이기 때문.

2. 정렬된 벡터의 0번째 인덱스를 무조건 포함하고 시작하므로, 반복자 i를 1부터 시작하도록 한다. 0부터 시작할 경우, 중복이 생길 수 있다.

Code