조잡하게 풀어보기

문제 출처 - 프로그래머스

문제 설명

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한 사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입출력 예

jobs가 [[0, 3], [1, 9], [2, 6]] 로 주어질 때 결과는 9가 나와야 한다.

보자마자 힙큐를 써야겠다는 생각은 했지만 막상 코드가 떠오르지 않았다.
몇 시간이나 쓸 문제는 아니었는데 풀다보니 3시간 잡아먹은 것 같다.
캐시로 현재 작업을 진행하려는 시간과 현재 작업이 걸리는 시간을 계속 기록해야만 했다.
클래스를 만드는 것도 나쁘진 않을 것 같다.

아무리해도 코드가 깔끔하지가 않다.

import heapq

def get_possible_jobs(jobs,start,end):
    return list(filter(lambda i: start<i[0]<=end, jobs))
    

def solution(jobs):
    jobs.sort()
    
    ans = [0]
    l = len(jobs)
    start,end = -1, jobs[0][0]
    heap = []
    
    while len(ans) <= l:
        for i in get_possible_jobs(jobs,start,end):
            heapq.heappush(heap, (i[1], i[0]))

        if len(heap) > 0:
            t, rq = heapq.heappop(heap)
            start = end
            end += t
            ans.append(ans[-1] + end - rq)
        else:
            end += 1
            
    return ans[-1]//l