1374번: 강의실 (acmicpc.net)

## 풀이
처음에는 수업이 남지 않을때까지 계속해서 강의실에 수업을 배치해주는것으로 생각했다. 그게 첫번째 코드
두번째 코드는 heapq를 사용해서 O(nlogn) 시간에 해결하는것

## code
import sys
input = sys.stdin.readlines
l = list(map(lambda x:x.rstrip().replace('\x1a',''),input()[1:]))

# l2는 강의가 끝시간, 시작시간, 강의번호으로 이루어진 리스트
l2 = []
for tmp in l:
    tmp_spl = tmp.split()
    l2.append([int(tmp_spl[2]),int(tmp_spl[1]),int(tmp_spl[0])])

# 끝나는 시간 기준 정렬
l2.sort()

# 한 강의실에 최대의 수업을 배치, 남은 수업의 리스트만 반환
def set_lecture_max_in_one_room (l):
    # 수업을 배치한다
    lecture = []
    lecture.append(l[0])
    for tmp in l:
        if tmp[1] >= lecture[-1][0]: #시작시간은 배치된 강의의 끝시간보다 같거나 커야 배치 가능
            lecture.append(tmp)
        else:
            continue

    not_set = []
    for tmp in l:
        if tmp not in lecture:
            not_set.append(tmp)
    return not_set

# 남은 수업이 0이 될때까지 반복해서 강의실 하나에 수업을 배치한다.
room_count = 0
while(True):
    if len(l2) == 0:
        break
    l2 = set_lecture_max_in_one_room(l2)
    room_count += 1

print(room_count)
처음 제출한것, 시간초과
시간복잡도 따지면서 문제풀자


import sys, heapq
input = sys.stdin.readlines
l = list(map(lambda x:x.rstrip().replace('\x1a',''),input()[1:]))

# l2는 강의가 끝시간, 시작시간, 강의번호으로 이루어진 리스트
l2 = []
for tmp in l:
    tmp_spl = tmp.split()
    l2.append([int(tmp_spl[1]), int(tmp_spl[2])])

# 끝나는 시간 기준 정렬
l2.sort()

def set_lecture_max_in_one_room (l):
    room_end_times = []

    heapq.heappush(room_end_times, l[0][1])

    for i in range(1,len(l)):
        if l[i][0] >= room_end_times[0]: # 배치된 수업의 끝 시간보다 새로 시작시간이 크거나 같아야 가능
            heapq.heappop(room_end_times) #끝난 수업 제거

        # 현재 수업의 끝나는 시간을 큐에 추가
        heapq.heappush(room_end_times, l[i][1])

    return len(room_end_times)

room_count = set_lecture_max_in_one_room(l2)

print(room_count)


heapq사용
...