백준 1931 회의실 배정 (python)

문제

출처: https://www.acmicpc.net/problem/1931

풀이

제 코드는 다음과 같습니다.

import sys

N = int(sys.stdin.readline().rstrip())
a = []

for i in range(N):
    start, end = map(int, sys.stdin.readline().split())
    diff = end - start
    a.append([start, end, diff])

a.sort(key=lambda x:(x[1], x[0], x[2]))

end = a[0][1]
count = 1

for i in range(1, N):
    if end <= a[i][0]:
        #print(a[i])
        end = a[i][1]
        count += 1

print(count)

이 문제는 회의실 사용표를 통해 회의가 가능한 최대 개수를 찾는 문제이다. 그리디 알고리즘을 통해 가장 빨리 끝나는 회의를 선택하고 바로 시작하는 회의를 찾으면 됩니다.

저는 입력값을 보고 끝나는 시간 기준으로 정렬이 되어있길래 정렬이 된 상태로 입력이 되는 줄 알고 따로 정렬을 해주지 않았습니다

그런데 8%에서 틀렸습니다 라고 결과가 나오길래 바로 정렬을 해주었습니다.

먼저 end 와 start로 데이터를 구분지어 받고 a라는 리스트에 회의 시간을 넣어주었습니다. 그리고 처음에는 시작하는 시간보다 두 시간의 차이가 적을 수록 많은 회의를 배정할 수 있다고 생각하여 diff 라는 변수를 선언하고 그 변수를 2순위로 a를 정렬하였습니다.

하지만 다음과 같은 경우 회의를 지나치는 경우가 있어 시작시간을 2순위로 하고 두 회의시간의 차이를 3순위로 하여 정렬을 했습니다. 4 4 4 5 5 5 이 경우 만약 두 시간의 차이를 2순위로 정렬하였다면 4 4 5 5 4 5 순으로 정렬이 되어 4 5 는 선택하지 못하여 최대 회의 개수를 찾지 못했습니다.

이번 문제는 시간이 오래 걸렸어도 참조 없이 제 스스로 문제를 해결하였습니다.