문제
김교수는 강의실 1개에 최대한 많은 강의를 배정하려고 한다. 배정된 강의는 서로 겹치지 않아야 하며 수업시간의 길이와 상관없이 최대한 강의를 많이 배정하라.
단, 두 강의의 시작시간과 종료시간은 겹쳐도 된다.
입력
첫 번째 줄에 강의 개수 N이 주어진다. 번째 줄에는 i번째 강의의 시작 시간 와 종료 시간 가 주어진다.
입력은 다음 조건을 만족한다.
인 정수
출력
첫 번째 줄에 최대 강의 수를 출력하라.
예시
입력
3
1 3
2 4
3 5
Plain Text
복사
출력
2
Plain Text
복사
정답
import sys
import heapq
N = int(sys.stdin.readline())
course = []
chosen = []
for _ in range(N):
s, f = list(map(int, sys.stdin.readline().split()))
heapq.heappush(course, (f,s)) # 힙 자료구조로 저장: 종료 시간을 기준으로 오름차순 정렬해야 하므로 종료 시간을 앞에 둠
current = heapq.heappop(course)
answer = 1
# 모든 course를 pop 하면서 확인
while course:
tmp = heapq.heappop(course)
if tmp[1] >= current[0]: # pop한 course의 시작시간이 마지막 선택된 course의 끝나는 시간보다 늦는 경우
current = tmp # 채택
answer += 1 # 강의 수 +1
print(answer)
Python
복사
풀이
•
•
따라서 종료시간이 짧은 순서대로 정렬하고
1.
가장 빨리 끝나는 강의 선택
2.
선택된 강의의 종료시간보다 시작시간이 같거나 큰 강의들 중 가장 빨리 끝나는 강의 선택
을 강의가 남지 않을 때까지 반복하면 된다.
•
그런데 다른 방식으로 풀면 시간초과가 나기 때문에 힙 자료구조로 풀어야 한다.
•
강의들을 종료 시간을 기준으로 오름차순 되도록 힙 자료구조로 만들자.
•
이때 힙 자료구조는 push 되는 원소의 첫 원소를 기준으로 오름차순되기 때문에 (종료시간, 시작시간) 의 형태로 강의들을 힙 자료구조에 넣어준다.
for _ in range(N):
s, f = list(map(int, sys.stdin.readline().split()))
heapq.heappush(course, (f,s)) # 힙 자료구조로 저장: 종료 시간을 기준으로 오름차순 정렬해야 하므로 종료 시간을 앞에 둠
Python
복사
•
이제 강의들을 하나씩 pop하면서 pop된 강의의 시작시간이 현재 선택된 강의 시간의 종료 시간보다 같거나 늦으면 현재 강의로 선택하고 강의 수를 + 1 해주는 것을 반복한다.
current = heapq.heappop(course)
answer = 1
# 모든 course를 pop 하면서 확인
while course:
tmp = heapq.heappop(course)
if tmp[1] >= current[0]: # pop한 course의 시작시간이 마지막 선택된 course의 끝나는 시간보다 늦는 경우
current = tmp # 채택
answer += 1 # 강의 수 +1
Python
복사
•
answer를 print 하면 한 강의실에서 들을 수 있는 최대 강의의 개수가 나온다.