[백준 1931] 회의실 배정

그리디 알고리즘이 정렬 알고리즘과 같이 묶여 나오는 문제입니다.

그리디 알고리즘은 어떠한 상황에서 그때그때 제일 좋은 선택을 하는 알고리즘으로,
문제 풀이에 정렬 알고리즘이 같이 쓰이는 경우가 많습니다.
본 문제도 그러한 경우에 해당합니다.

문제 구문 해석

본 문제에서 주목할 부분은 다음과 같습니다.

• 회의는 한번 시작하면 중간에 중단될 수 없으며
  한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
  회의의 시작시간과 끝나는 시간이 같을 수도 있다.

첫째, 회의는 한번 시작하면 중간에 중단될 수 없습니다.
중간에 끊기는 경우 없이 그냥 시작, 끝 시간을 기준으로 생각하면 됩니다.

둘째, 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있습니다.
예를 들어,

1 4
4 5

회의 시간이 위와 같이 주어졌다면, 첫 번째 회의가 끝나는 동시에 두 번째 회의가 시작될 수 있음을 의미합니다.

셋째, 회의의 시작시간과 끝나는 시간이 같을 수도 있습니다.
예를 들어,

1 1
1 1

회의 시간이 위와 같이 주어졌을 때,
두 회의 모두 수행되므로 답은 2를 출력해야한다는 것을 의미합니다.

정렬 방법 파악

최대의 회의 개수를 알기 위해서는 빨리 끝나는 회의 순서대로 정렬을 해야합니다.
빨리 끝나야 뒤에 회의를 하나라도 더 할 수 있기 때문입니다.

또한, 끝나는 시간이 같은 경우가 있을 수 있으므로 시작 시간의 오름차순으로 2차 정렬이 필요합니다.
예를 들어,

2 2
1 2

끝나는 시간은 2로 모두 동일하지만,
첫 번째 회의가 먼저 수행된다면 두 번째 회의는 시작할 수 없게 됩니다.
하지만, 회의를 최대한 많이 하기 위한 방법으로는 두 번째 회의를 먼저 하고난 뒤에 첫 번째 회의를 수행하는 방법이 존재합니다. ((1, 2)를 먼저 수행하고 시간이 2가 되면 (2, 2)를 수행할 수 있습니다.)

모두 종합해보면, 다음과 같습니다.
끝나는 시간으로 1차 오름차순 정렬, 시작하는 시간으로 2차 오름차순 정렬이 필요합니다.

Python에서는 조건 기준이 여러개일 때에 sort 함수에 key를 괄호로 묶어 설정합니다.
이 점을 참고한 풀이 코드는 다음과 같습니다.

문제 : 백준 1931 - 회의실 배정