Softeer - 강의실 배정 (Python)

Lv3, ⭐⭐⭐

문제 풀이

• 자주 접하던 강의실 배정 문제
• 대표적인 Greedy 알고리즘 문제이다.

Sol 1) sort()를 통한 풀이

• 2345 ms의 시간 소요
• 당연히 시간초과가 날 줄 알았는데 제한시간이 5초라서 널널했던건가....

from sys import stdin
n = int(stdin.readline())
lectures = []
for _ in range(n):
    s, f = map(int, stdin.readline().split())
    lectures.append([s, f])

lectures.sort(key = lambda x : x[1])
cnt = 1
last = lectures[0][1]

for i in range(1, n):
    if last <= lectures[i][0]:
        cnt += 1
        last = lectures[i][1]
    else:
        continue

print(cnt)

Sol 2) heapq를 통한 우선순위 큐 풀이

• 1697 ms의 시간 소요
• 정석 풀이, 확실히 이전 풀이보다 시간 소요가 줄어든 모습이다.

from sys import stdin
import heapq
n = int(stdin.readline())
lectures = []
for _ in range(n):
    s, f = map(int, stdin.readline().split())
    heapq.heappush(lectures, (f, s))

cnt = 1
last = heapq.heappop(lectures)[0]

while lectures:
    now = heapq.heappop(lectures)
    if last <= now[1]:
        cnt += 1
        last = now[0]
    else:
        continue
print(cnt)