https://www.acmicpc.net/problem/11000
시간 1초, 메모리 256MB
input :
- N(1 ≤ N ≤ 200,000)
- Si, Ti(1 ≤ Si < Ti ≤ 109)
output :
- 강의실의 개수를 출력
조건 :
- Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
- 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
이번엔 강의를 많이 듣는게 아닌, 강의실을 얼마나 사용할 것인가를 체크하는 것이다.
우선 강의 들끼리 겹치는 경우가 발생하는 경우 강의실이 늘어나야 한다.
겹치는 경우는 강의가 끝나는 시간이 시작하는 시간보다 큰 경우이다.
보면 강의가 시작하는 시간 순서대로 정렬을 해야 겹치는 개수를 확인할 수 있다.
끝나는 시간대로 할 경우에 시작하는 강의의 수가 뒤섞여 버리게 됨.
가장 큰 문제였던 것은 계속 회의실 배정 문제 처럼 생각을 한다는 것이다.
그냥 다른 문제인데 계속 저거에 얽매여 있으니까 당연히 문제를 못 풀지....
모든 강의를 듣는다? 들으려 하는 것이 아닌 강의실을 배정하는 것 한 강의실에서 할 수 있는 강의인가를 확인하다가 불가능하면 늘려나가는 방식을 사용하자.
어차피 모든 강의를 해야하는데 그렇다면 중요한 것은 무엇일까?
이 강의가 언제 시작하는 지를 가지고 비교를 해야 하는 것이다.
우선순위큐를 이용해서 현재 배치해놓은 강의들 중에 가장 빨리 끝나는 시간이 무엇인지 가져와 비교를 한 후 강의를 이어 할 수 있을 경우에는 이 시간을 업데이트 해준다.
그렇지 않은 경우엔 새로운 강의실을 생성해야 하기 때문에 이 시간을 추가해 준다.
import sys
import heapq
n = int(sys.stdin.readline())
data = []
for i in range(n):
s, t = map(int, sys.stdin.readline().split())
data.append((s, t))
data.sort(key=lambda x:(x[0], x[1]))
q = []
heapq.heappush(q, data[0][1])
for i in range(1, n):
time = q[0]
if time > data[i][0]:
# 연강이 불가능 한 경우 새로운 시간을 추가한다.
heapq.heappush(q, data[i][1])
else:
heapq.heappop(q)
heapq.heappush(q, data[i][1])
print(len(q))
