[백준] 11000 : 강의실 배정 (파이썬)

스위핑, 우선순위큐, 그리디 문제

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

---

💡 풀이코드 (성공 - 스위핑)

import sys 
import heapq 

n = int(sys.stdin.readline())
lecture = []
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    heapq.heappush(lecture, (a, 1)) # start 
    heapq.heappush(lecture, (b, 0)) # end 

cnt = 0
ans = 0
while lecture:
    a, b = heapq.heappop(lecture)
    if b == 1:
        cnt += 1
    else:
        cnt -= 1

    ans = max(cnt, ans)
print(ans)

---

💡 풀이코드 (실패 - 우선순위큐, 그리디)

import sys 
import heapq 

n = int(sys.stdin.readline())
lectureH = []
lecture = []
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    heapq.heappush(lectureH, (b, a)) # end, start
    heapq.heappush(lecture, (b, a)) 
    
ans = 0

while lectureH:
    end, start = heapq.heappop(lectureH)

    cnt = 0
    while lecture and end > lecture[0][1]:
        heapq.heappop(lecture)
        cnt += 1
    ans = max(ans, cnt)

print(ans)

---

💡 풀이코드 (성공 - 우선순위큐, 그리디)

import sys
import heapq

n = int(sys.stdin.readline())
lecture = []

for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    heapq.heappush(lecture, (a, b))  

end_times = []
ans = 0

while lecture:
    start, end = heapq.heappop(lecture)

    while end_times and end_times[0] <= start: # 현재 진행 중인 강의 중에서 끝난 강의는 제거
        heapq.heappop(end_times)

    heapq.heappush(end_times, end) # 현재 강의의 종료 시간을 추가

    ans = max(ans, len(end_times)) # 동시에 진행 중인 강의 수의 최대값 갱신
print(ans)

---

참고문헌

https://eunsun-zizone-zzang.tistory.com/64

[백준/파이썬] 11000 : 강의실 배정

https://hongcoding.tistory.com/79

[백준] 11000 강의실 배정 (Python 파이썬)