[Python 3] BOJ - 1931 "회의실 배정"

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

1931번: 회의실배정

 

 # 풀이:

개인적으로 이 문제의 핵심은 그리디 알고리즘 문제라는 것과 정렬 기준을 세우는 것이다. 현재 i번째 회의를 선택한다고 하자. 이미 회의의 갯수는 정해져 있으므로 더 많은 회의를 진행하기 위해서는 i의 끝나는 시간과 i + 1의 시작되는 시간의 간격이 크면 클수록 더 많은 회의를 진행할 수 있다. 따라서 빨리 끝나는 회의일 수록 간격이 더 크다. 만일 끝나는 시간이 같다면, 일찍 시작하는 회의일 수록 간격이 더 커져 많은 회의를 진행 할 수 있다. 따라서, 회의를 정렬할 때 우선적으로 끝나는 시간이 빠른 순으로 정렬하되, 끝나는 시간이 같다면 시작하는 시간이 더 이른 순으로 정렬해야 정답을 올바르게 구할 수 있다.

 

 # 코드

import sys, functools

# compare : 첫번째 인자를 오름차순으로, 같다면 두번째 인자를 오름차순으로 정렬하는 함수
def compare(x,y):
    if x[1] < y[1]:
        return -1
    elif x[1] > y[1]:
        return 1
    else:
        if x[0] < y[0]:
            return -1
        elif x[0] > y[0]:
            return 1
        else:
            return 0

# 입력부
n = int(sys.stdin.readline())
meeting = []
for i in range(n):
    start, end = map(int, sys.stdin.readline().split())
    meeting.append((start, end))
    
# 정렬
meeting.sort(key=functools.cmp_to_key(compare))

idx = 0
now_start, now_end = meeting[idx][0], meeting[idx][1]
ans = 1
while idx < len(meeting) - 1:
    idx += 1
    next_start, next_end = meeting[idx][0], meeting[idx][1]
    if next_start >= now_end:
        now_start, now_end = next_start, next_end
        ans += 1
print(ans)