[Softeer] 소프티어 강의실 배정(python)

문제)

 

 

알고리즘)

* 해당문제는 백준에 "회의실 배정"이란 이름의 문제 비슷합니다.

- 목표는 가장 많이 강의실 배정을 하는 것

- 처음에는 sorted, lambda를 사용하여 진행했으나 시간 초과!!

- heapq를 사용하여 각 입력시간에서 fin시간이 이른 시간부터 정렬

- 그후 기준점 과 수업 시작시간과 비교하여 사용가능하다면 cnt하고 v를 해당 start로 갱신

 

이를 입력부에서 받은 모든 값을 돌리고 최종 cnt 출력 

 

 

코드)

import sys
import heapq
input = sys.stdin.readline

n = int(input())

time = []
w = 0 #기준
cnt = 0 #강의실 수 카운트

for _ in range(n):
    start, fin = map(int, input().split())
    heapq.heappush(time, (fin, start))

while time:
    f, s = heapq.heappop(time)

    if s >= w: #기준시간보다 start시간이 늦는다면 사용가능
        cnt += 1
        w = f

print(cnt)

 

비슷한 문제)