[파이썬 | BOJ | 1374] 강의실

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

1374번: 강의실

문제

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 개수 N(1≤N≤100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이라고 가정한다.

출력

첫째 줄에 필요한 최소 강의실 개수를 출력한다.

풀이

기본적인 유명한 그리디 알고리즘을 기반으로 풀 수 있다. 하지만 이러면 시간 초과가 난다.

 

1번 (3, 8)

2번 (7, 13)

3번 (2, 14)

4번 (12, 18)

5번 (6, 20)

6번 (15, 21)

7번 (20, 25)

8번 (6, 27)

 

따라서 시간이 1부터 점점 증가하면서, 해당 강의의 시작시간보다 크거나 같아지면, list에 넣고, 그 강의의 종료시간보다 커지면, list에서 뺀다.

위에 그림에서 빨간색글이 시간이기에, time == 2가 되면, 3번 강의를 list에 넣고, time == 3이 되면 1번 강의를 list에 넣는다.

 

모든 시간이 지나고나서, 가장 list의 크기가 컸던 시점이, 최소한의 강의실의 개수이다.

 

 

	# [파이썬 | BOJ | 1374] 강의실
	import sys
	from collections import deque
	read = sys.stdin.readline
	ans = -1
	N = int(read())
	startTime = []
	endTime = []
	for i in range(N):
	a, b, c = map(int, read().split())
	startTime.append([b, a])
	endTime.append([c, a])
	startTime.sort(reverse = True)
	endTime.sort(reverse = True)
	temp = []
	for time in range(endTime[0][0]+1):
	while startTime and time >= startTime[-1][0]:
	t, idx = startTime.pop()
	temp.append(idx)
	while endTime and time >= endTime[-1][0]:
	t, idx = endTime.pop()
	temp.remove(idx)
	if len(temp) > ans:
	ans = len(temp)
	#print(time, temp)
	print(ans)

view raw BOJ1374.py hosted with ❤ by GitHub