악곱 == 악성곱슬

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

---

해당 문제는 그리디 문제이다. 다만, 그리디 라는 것이 복잡한 구조안에 숨겨져 있는 문제이다.

해당 문제를 그리디로 풀게 된 정당성은 다음과 같다.

• Ti < Sj 일 경우 i 와 j 수업은 같이 들을 수 있다.
• 시작 시간(Si)을 기준으로 정렬을 하고, 이를 순차적으로 min-heap에 끝나는 시간(Tj)를 기준으로 push한다. 그렇게 되면 먼저 시작하는 시간은 강의실 하나를 배정하는 효과를 얻고, 끝날 때까지 min-heap 구조에 남게 되면서 강의실을 차지하는 효과를 얻는다. 이를 통해 min-heap의 최대 크기를 구하면 강의실이 가장 많이 겹치는 개수를 자연스레 구할 수 있게 된다.

최대한 많이 겹치는 순간을 구하기 위해 max_count를 사용하여 기억하고 있는 부분에서 정렬을 통한 그리디 라고 볼 수 있다. 복합적으로 어려운 그리디 문제이다.

입력이 20만이고, 시간의 크기가 10^9이다. 시간에 대한 완전탐색으로 구한다면 시간초과가 발생할 것이다. 따라서 크기가 클 때는 여러 자료구조를 머리에 떠올리자. → 트리구조 (우선순위 큐, 이진 탐색 등)

heapq를 이용한 코드는

import sys
import heapq

def solution(classroom, n):
    # 우선순위큐 사용
    # 입장 시간을 기준으로 정렬 해야 하는 문제
    classroom.sort(key=lambda x: (x[0], x[1]))
    max_count = 1
    heap = []
    # min-heap 을 사용하는데, 여기서 key 는 끝나는 시간으로 정렬을 해야함.
    heapq.heappush(heap, (classroom[0][1], classroom[0][0]))
    for i in range(1, n):
        while heap[0][0] <= classroom[i][0]:
            heapq.heappop(heap)
            if len(heap) == 0:      # heap 이 비어 있는 경우에 대한 예외처리
                break
        heapq.heappush(heap, (classroom[i][1], classroom[i][0]))
        tmp = len(heap)
        if tmp > max_count:     # 매 순간 min-heap 의 크기에 대한 그리디 알고리즘
            max_count = tmp
    return max_count

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