[프로그래머스] - 디스크컨트롤러[인터벌 스케쥴링][파이썬]

https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

 

---

해설

힙과 인터벌 스케쥴링(처음 들어보았다)의 개념을 갖고 푸는 문제라고 한다.

일단 인터벌 스케쥴링은 greedy algorithm 쪽에 속한다.

일단 기본 개념은 간단하다. 

위의 문제와 같이 시작점과 끝점이 주어질때 가장 빠르게 일을 종료하는 방법을 찾는 것이다.

흔히 4가지의 케이스로 나누어서 보는데 다음과 같다. 

(내용은 https://snupi.tistory.com/34 에서 가져왔다.)

 

1. 일의 시간이 가장 짧은 순서대로 ? (Shortest interval)

시간이 가장 짧은 일이,

맨 뒤의 일이라면 비효율적이게 된다

 

2. 시작시간이 빠른 순서대로 ? (Earliest start time)

시작시간이 가장 빠른 일이,

가장 늦게 끝나면 비효율적이게 된다

 

3. 겹치는 일이 가장 적은 순서대로 ? (Fewest conflicts)

이 역시 쉽게 반례를 들 수 있다

 

그렇다면, 하나의 정렬만으로는 이 사건을 해결할 수 없는 것일까?

아니다

 

4. 끝나는 시간이 빠른 순서대로 (Earliest Finish Time)

이와 같은 방법이면, 반례를 찾을 수 없다

또한 러닝타임은 sorting하는 데에 O(nlogn)이고 카운팅 하는 데에 O(n)이므로

O(nlogn)의 러닝타임을 갖는다 

 

그럼 여기서 끝나는 시간이 가장 빠른 시간대로 해야 하는데 다만 이 문제에서 요청 시간인 것이지 시작 시간이 아니라는 것이다.

예를 들어 [2,6]의 경우 2초에 요청이 들어온거지 2초에 시작해서 6초에 끝나는게 아닌것이다.

즉 2초 이후의 어떤  x초에 일을 시작하여 x + 6초에 일이 끝난다는 것이다.

 

그러면 x를 어떻게 결정하냐? 이건 선행 작업의 종료 시간이 되는 것이다. 

즉 [[0,6],[2,6]] 의 경우 x는 6이 된다. 이렇게 선행 작업의 종료시간에 맞추어 요청이 들어온 일 중 끝나느 시간이 가장 빠른 시간대의 힙을 구성해야 한다. 

 

기본 개념은 다음과 같다.

1. jobs를 요청 시간의 순으로 정렬한다. 

2. time(현재 시간, 0부터 시작)에 맞추어 요청이 들어온 일을 힙에 거꾸로 뒤집어서 넣는다.

[2,6] -> [6,2] 이유는 이래야지 작업 종료 시간의 순으로 힙이 구성되기 때문이다.

2-2. 만약에 현재 time보다 빠르거나 같은 시간대가 없다면 남아 있는 jobs 중에 가장 빠른 시간대로 time을 옮긴다.

 

3. 현재 시간대에 작업가능한 일들을 전부 담았다면 heap의 루트의 일을 처리한다.

그러면 time +  heap.pop() 만큼의 시간이 된다.

 

4. 2 ~ 3 이 heap과 jobs가 빌때까지 반복한다.

import heapq


def solution(jobs):
    answer = 0
    time = 0
    length = len(jobs)
    jobs.sort() # 요청 시간 순으로 정렬
    heap = []
    while len(jobs) != 0 or len(heap) != 0:

        while len(jobs) != 0 and jobs[0][0] <= time: # job에 요청시간이 현재 시간보다 작은 것들을 힙에 넣음
            s,w = jobs.pop(0)
            heapq.heappush(heap,[w,s]) #힙에 뒤집어서 넣음

        if len(heap) == 0: #힙이 비어있다면 현재 시간에 처리할 수 있는 일이 없다는 것 그러므로 타임으로 미래로 땡김
            time = jobs[0][0]
            continue

        workTime, startTime = heapq.heappop(heap)
        answer += time + workTime - startTime #요청 부터 종료시간까지 더함
        time += workTime #작업 시간 만큼 시간이 지났음


    return answer // length