[백준] 강의실 배정

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

11000번: 강의실 배정

그리디 문제입니다. 첫 접근은 빨리 끝나는 강의가 우선순위 큐에서 먼저 나오도록 풀이했습니다. 빨리 끝나는 강의와 겹치는 강의들이 있다면 강의실이 추가적으로 필요하게 됩니다. 만약 겹치지 않는 강의를 만나게 되면 현재 강의가 진행되는데 필요한 강의실의 최대 개수를 갱신시켜주고 해당 강의부터는 이어질 수 있으므로 cnt를 1로 초기화시켜 줍니다. 하지만 이렇게 풀이했을 때의 문제가 있습니다. 

6

1 4

4 8

3 5

5 6

6 8

7 8

해당 케이스에서 문제가 발생하는데 한번 보시면 좋을 것 같습니다.

 

import heapq, sys

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())

lecture = []

q = []

for i in range(n):
    start, end = tuple(map(int, input().split()))
    heapq.heappush(q, (end, start))

max_cnt = 1
cnt = 1
# 가장 빨리 끝나는 강의실의 시간을 저장
cur = q[0][0]

heapq.heappop(q)

while q:
    end, start = heapq.heappop(q)
    if start < cur:
        cnt += 1
        continue

    max_cnt = max(cnt, max_cnt)
    cnt = 1
    cur = end
max_cnt = max(cnt, max_cnt)

print(max_cnt)

 

정답 풀이입니다. 이번에는 강의가 빨리 시작한 순으로 정렬해주고 탐색을 해줍니다. 현재 강의가 시작했을 때 끝난 강의가 있으면 우선순위 큐에서 다 빼주면 됩니다. 그리고 현재 강의가 끝나는 시간을 넣어주면 됩니다. 이렇게 되면 현재 강의가 진행되고 있을 때 필요한 강의의 수가 우선순위 큐에 유지가 되게 되고 각 순간에서 필요한 강의실 수중 최대가 답이 되게 됩니다. 

 

import heapq, sys

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())

lecture = []
q = []

for i in range(n):
    lecture.append(tuple(map(int, input().split())))

# 강의가 시작하는 순서대로 정렬한다.
lecture.sort()

ans = 0

for start, end in lecture:
    # 큐에 끝난 강의실이 있으면 제외시켜준다.
    while q and q[0] <= start:
        heapq.heappop(q)
    heapq.heappush(q, end)

    ans = max(ans, len(q))


print(ans)