[그리디] 백준 회의실 배정 1931번 with Python3

 

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

1931번: 회의실 배정

문제

 

내 풀이 -실패-

import sys
input = sys.stdin.readline
n = int(input())

tmt = [list(map(int, input().rstrip().split())) for _ in range(n)]

tmt.sort()

ans = []
check = 0
chk2 = 0


for i in range(n):
    if check <= tmt[i][0] and check != tmt[i][1]:
        if tmt[i][0] == tmt[i][1] and tmt[i][0] == chk2:
            continue

        A, B = map(int, tmt[i])
        temp = [B-A, i]

        for j in range(i+1, n):
            if (A == tmt[j][0] and A == tmt[j][1]) or (B == tmt[j][0] and B == tmt[j][1]):
                chk2 = max(A, B, chk2)
                ans.append(tmt[j])
            elif tmt[j][0] < B:
                temp = min(temp, [tmt[j][1] - A, j])
            else:
                break

        ans.append(tmt[temp[1]])
        check = tmt[temp[1]][1]

print(len(ans))

해설

94%정도에서 계속해서 틀렸다고 나왔다.

기본적으로 회의 시작시간을 오름차순으로 정렬한뒤에 특정 시간을 골라서 해당 회의가 끝나는 시간보다 빨리 끝나는 시간이 있으면 그것을 선택하는 식의 알고리즘이다. 

 

 

정답 풀이

import sys

N = int(sys.stdin.readline())

time = [[0]*2 for _ in range(N)]
for i in range(N):
    s, e = map(int, sys.stdin.readline().split())
    time[i][0] = s
    time[i][1] = e

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

cnt = 1
end_time = time[0][1]
for i in range(1, N):
    if time[i][0] >= end_time:
        cnt += 1
        end_time = time[i][1]

print(cnt)

출처:https://suri78.tistory.com/26

 

해석

정답과 그래도 유사하게 접근을 하긴 했던거 같다. 하지만 내 코드는 여러 반례들을 위한 추가 조건들이 덕지덕지 붙어있던 반면 정답은 정확히 문제에 맞는 탐욕법을 구상해 진행된다.

 

주요 포인트는 끝나는 시간을 내림차순으로 정렬한 뒤에, 이를 기준으로 시작시간을 오름차순으로 다시 정렬한다는 것이다.