백준 1931번: 회의실 배정 (파이썬, 그리디 알고리즘)

그리디 알고리즘 문제의 유명한 예시이다. 그리디 알고리즘을 풀기 위해서는 최적해를 구해야하는데, 최적해라는것을 증명하기가 쉽지 않아 대부분 풀이를 떠올리고 반례를 생각해보는것 같다.

반례가 없으면 최적해라고 생각하는 것이다.

 

나도 처음에는 단순하게 끝나는 시간을 기준으로 정렬하였다. 그러나 끝나는 시간순으로 답을 골랐을때는 틀렸었다.

왜인지를 계속 고민했는데 예시에만 집중하여 끝나는시간에 중복이 있을수도 있다는 생각을 간과한 것이다.

 

따라서 lambda식으로 끝나는시간으로 먼저 정렬 후 그다음 정렬 순위로 시작하는 시간을 주었다.

그렇게 정렬 후 첫번째 끝나는 시간보다 큰 시간이 있으면 그 시간을 고르는 식으로 알고리즘을 짜주었더니 맞았다.

   

import sys

num = int(sys.stdin.readline())  # 세로 길이 설정
board_pre = []
for _ in range(num):
    board_pre.append(list(map(int, sys.stdin.readline().split())))

ans = 1

board = sorted(board_pre, key=lambda x: (x[1], x[0]))

max_ = board[0][1]

for i in range(1, num):
    if board[i][0] >= max_:
        ans += 1
        max_ = board[i][1]

print(ans)