-풀이
import sys, heapq
input = sys.stdin.readline
cnt = 0
count = []
answer = []
N = int(input())
for i in range(N):
a = list(map(int,input().split()))
answer.append(a)
answer.sort()
for j in range(len(answer)):
if len(count) == 0:
#회의 끝나는 시간 count에 저장
heapq.heappush(count, answer[j][1])
cnt += 1
else:
#회의 끝나는 시간보다 시작시간이 빠르면
if answer[j][0] < count[0]:
heapq.heappush(count, answer[j][1])
cnt += 1
else:
heapq.heappop(count)
heapq.heappush(count, answer[j][1])
print(cnt)
-풀이 설명
바로 전에 풀었던 콘센트 문제와 비슷한 유형의 문제로, 강의가 끝나는 시간을 count리스트에 담고 각 각 수업 시작시간과 비교하여 강의가 끝나는 시간보다 시작시간이 더 빠를경우 강의실을 하나 더 만들고, 반대라면 강의가 끝나는 시간을 갱신해준다.
ps. if answer[j][0] < count[0]: 이부분이 약간 헷갈렸다. 왜냐하면 count[0] 값만 계속 가져오기 때문이다. 그러나 조금씩 실험해보면서 생각해보니 heapq를 이용하면 heappush를 할 때 자동적으로 이진트리 최소힙으로 정렬이 되기 때문에 항상 count[0]값과 비교해도 최소의 끝나는 시간으로 대조할 수 있었다.
'알고리즘' 카테고리의 다른 글
[그래프탐색/브루트포스] 백준 14502 파이썬 (연구소) 골드5 (0) | 2022.06.06 |
---|---|
[그리디] 백준 2217파이썬 (로프 ) 실버4 (0) | 2022.06.04 |
[그리디/정렬/우선순위큐] 백준 23843 파이썬 (콘센트) 골드5 (0) | 2022.06.02 |
[백트래킹] 백준 9663 파이썬 (N-Queen) 골드5 (0) | 2022.06.01 |
[기하학/다각형] 백준 2166 파이썬 (다각형의 면적) 골드5 (0) | 2022.05.31 |