회의실 배정-1931

처음의 회의 개수가 주어지고 각 줄마다 회의 시작 시간과 끝나는 시간이 주어진다. 시간은 겹치면 안된느데 단, 끝나는 시간과 시작하는 시간이 겹치는 경우는 허용한다. 즉 끝나는 시간과 동시에 시작할 수 있다는 것이다.

잘 생각해보자. 일단 끝나는 시간이 작으면 작을수록 최대한 많은 회의를 할 수 있을 것이다. 그러면 시작 시간과 끝나는 시간을 같이 저장한 다음 끝나는 시간을 오름차순으로 정렬해주면 될 것이다.

하지만 단순히 끝나는 시간만 오름차순으로 정렬하면 정답으로 채택되지 않는다. 이런 경우를 생각해 보자.

5 4 4 4 4 3 4 2 4 1 4

정답은 3이지만 만약 종료시간만 정렬되어 있을 때는 정답이 2만 나올 수도 있다. 결론적으로 2번 째 요소로 먼저 오름차순으로 정렬한 다음에 같을 경우 첫 번째 요소도 오름차순으로 정렬해줘야 한다.

이 문제는 아마 이 부분 때문에 통과를 못하는 사람들이 많았을 것이다. 우연의 일치로 정렬이 되어서 통과한 사람도 있었을 것이다. 이러한 예외 케이스를 생각하는 것이 아마 프로그래밍 문제를 풀면서 가장 어려운 것 같다.