악곱 == 악성곱슬

그리디, 정렬, 우선순위큐

---

우선 전제 조건에 강의 시간은 0~10억 이기 때문에 아쉽지만 카운트 정렬은 사용할 수 없다. 만약 적당한 숫자였다면 그냥 카운팅 해서 최대값을 뽑았을 것이다.

그렇다면 다음 생각은 강의 러닝타임이 가장 적은 것부터 배치해보자는 아이디어이다. 그러나 이렇게 할 경우 빈 시간대를 찾는 과정에서 시간 복잡도가 너무 커진다.

따라서 세번째 아이디어는 시작시간을 순서대로 배치하고, 끝나는 시간만 저장해놓는다. 이때 빈 강의실이 없다면 새로운 강의실을 (리스트에)추가하는 아이디어이다. 그리고 리스트의 크기를 반환하면 답이 나올 것이다. 그러나 이렇게 해도, 시간 복잡도가 꽤 복잡해진다. 따라서 우리가 빈 강의실을 찾기 위해서 필요한 것은 끝나는 시간의 최소값 이므로 우선순위 큐를 사용하면 된다. 코드는 다음과 같다.

구현

---

import sys
import heapq

def solution(n):
    lec_room = []
    heapq.heappush(lec_room, 0)
    lec_info.sort(key=lambda x: x[1])
    for lec_num, lec_start, lec_end in lec_info:
        # 남는 강의 실이 있다면
        if lec_room[0] <= lec_start:
            heapq.heappop(lec_room)     # 남는 강의실 pop
            heapq.heappush(lec_room, lec_end)   # 새로 배정받은 강의의 끝나는 시간을 넣어줌
        # 남는 강의 실이 없다면
        else:
            heapq.heappush(lec_room, lec_end)
    return len(lec_room)

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    lec_info = []
    for _ in range(N):
        lec_info.append(list(map(int, sys.stdin.readline().rstrip().split())))
    print(solution(N))