[파이썬/python] 백준 1374번 강의실

import sys
N = int(sys.stdin.readline())
lec = list()
for i in range(N):
    num, start, finish = map(int, sys.stdin.readline().split())
    lec.append([start, finish])

lec.sort()

temp = [lec[0][1]]

index = 1
minFinish = temp[0]
while index < len(lec):
    if lec[index][0] < minStart:
        temp.append(lec[index][1])
        if minFinish > lec[index][1]:
            minFinish = lec[index][1]
    else:
        temp.sort()
        temp[0] = lec[index][1]
        if len(temp) == 1:
            minFinish = temp[0]
        else:
            minFinish = temp[1]

    index += 1

print(len(temp))

그리디 알고리즘

최소한의 강의실로 수업들을 채워넣는 알고리즘을 짜야 합니다.

 

lec list에 [start, finish]로 강의들을 저장한 후, 시작시간 기준으로 sort합니다.

 

1. '가장 빨리 시작하는 강의가 끝나는 시간'보다 시작 시간이 작은 강의들의 끝나는 시간을 temp에 삽입하며 끝나는 시간이 더 빠른 것을 minFinish에 저장합니다.

2. 'minFinish'보다 시작 시간이 늦는 경우(else문),

    - temp중 가장 작은 것을 현재 강의의 끝나는 시간으로 바꿔줍니다. ( 이어붙였다고 생각하시면 됩니다.)

    - 나머지 temp중 가장 작은 것을 minFinish에 저장합니다.

 

시간초과가 나서 당황했지만 이중포문 없이도 할 수 있더군요.

TIP: 이 코드는 minFinish = min(minFinish, lec[index][1]로 고칠 수 있겠습니다.