[heapq] 정원 입장은 선착순

문제

1부터 N까지 번호표를 든 N명의 사람들이 있습니다. i번 사람은

ai 시간에 정원 입구에 도착해서 ti 시간 동안 정원에 머무르다 갑니다. 정원에는 한 번에 한 명의 사람만이 들어갈 수 있으며, i번 사람이 정원 입구에 도착했을 때, 이미 누군가가 정원에 있다면 정원 안에 있는 사람이 떠날때 까지 기다렸다가 이후에 정원을 출입할 수 있습니다. 기다리는 사람이 여러명이라면 번호표의 숫자가 작은 사람부터 들어갈 수 있습니다. 모든 사람이 정원을 한 번씩 들려서 머물렀다 갈 때, 이들 중 가장 오래 기다려야 하는 사람이 기다리는 시간을 구하는 프로그램을 작성해보세요

예제 설명

4번 사람이 10 시간에 도착해 27 시간까지 정원에 머무르다가 갑니다.

4번 사람이 정원에 있을 때 1, 3번 사람이 정원 입구에 도착하는데 번호표의 숫자가 더 작은 1번 사람이 2 시간 기다려 27 시간에 정원에 출입합니다.

3번 사람은 1번 사람이 떠나는 30 시간까지 총 10 시간 기다렸다 정원에 출입합니다.

3번 사람은 80 시간까지 정원에 머무릅니다.

이후 100 시간에 5번 사람이 들어와 110 시간까지 머무르고, 그 사이에 2번 사람이 도착해 5 시간 기다렸다가 110 시간에 정원에 들어가서 140 시간까지 머무릅니다.

따라서, 가장 오래 기다린 사람은 10 시간 기다린 3번 사람입니다.

 

아이디어

1. 배열을 도착 순으로 정렬한다. 

2. 배열을 돌며 대기가 필요하지 않고 대기자가 있는 구간을 반복하며 현재 시간과 정답을 갱신한다. (대기자 힙큐 pop)

3. 대기가 필요 없고 (arrive > now) 대가자가 없으면 , 현재 시간만 갱신

4. 대기가 필요하면 힙큐에 번호순으로 삽입

 

코드

import heapq
import sys

INT_MAX = sys.maxsize
n=int(input())
q=[] #대기 리스트
arr=[]
ans=0


for i in range(n):
    arrive, time = map(int,input().split())
    arr.append((arrive,i,time))

#  마지막 사람까지 힙큐에 들어갈 경우 탐색을 위해 한 명 더 추가해줘야함.
arr.append((INT_MAX, n + 1, 0))

#도착 순 정렬
arr.sort()
now=0  # 현재 시간

for arrive, num, time in arr:
    #도착이 현재 시간보다 크고 대기자가 있으면 
    while arrive >= now and q:
        _, next_arrive, next_time = heapq.heappop(q)
        ans = max(ans, now - next_arrive)
        now+=next_time 

    #도착이 현재 시간보다 크고 대기자가 없으면 (대기 필요X = 대기시간이 0)
    if arrive >= now:
        #현재시간만 갱신
        now = arrive + time 
    #대기가 필요하면, 큐에 번호 순으로 삽입 
    else:
        heapq.heappush(q, (num, arrive, time))
    
print(ans)