[ProblemSolving] 백준 - 11000 강의실배정 (그리디, 힙)

문제 링크

문제 설명

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

예제 입력1

3
1 3
2 4
3 5

예제 출력1

2

풀이

시간 복잡도 고려

시간복잡도를 고려해 힙(우선순위큐)를 사용하여 문제를 해결했다.
데이터의 개수가 200,000이므로 O(NlogN)인 알고리즘을 설계해야한다.
200,000 * 약20 = 4,000,000의 연산은 1초 내에 충분히 해결할 수 있다.

풀이 순서

• 입력은 이차리스트 classes에 [[수업시작시간, 끝난시간], [시작시간, 끝난시간] ...] 으로 저장하고
  수업 시작 시간 기준으로 정렬한다.
• heap에는 첫번째 수업끝난시간을 저장한 후 반복문을 돌면서 비교한다.
  • 다음에 오는 수업 시작시간이 heap[0](힙의 0인덱스는 가장 작은 수를 반환)보다 작다면
    새로운 강의실이 필요하므로 heap에 수업 끝난시간을 추가해준다.
  • 그렇지 않다면, 이미 존재하는 강의실을 계속 사용가능하므로
    heap[0]을 pop하고 새로운 수업 끝난 시간을 추가한다.

코드

import heapq
import sys
input = sys.stdin.readline
n = int(input())
classes = []
for _ in range(n):
    classes.append(list(map(int, input().split())))
classes.sort()
heap = []
heapq.heappush(heap, classes[0][1])
for i in range(1, n):
    a, b = classes[i]
    if a < heap[0]:
        heapq.heappush(heap, b)
    else:
        heapq.heappop(heap)
        heapq.heappush(heap,b)
print(len(heap))