강의로 돌아가기
bongjinpark1

유휴중 작업 처리 순서 어떻게되나요?

입력이 [[0,9], [0, 4], [0, 3]] 일때, 최적해를 구하려면, 작업시간이 3, 4, 9인 순으로 처리해야되는데요.

CPU가 유휴상태일때는 가장 처음 들어온 요청을 먼저 처리한다고 하니까, index 기준으로 작업시간이 9인것을 먼저 처리하고, 다음으로 3, 4인 것을 처리해야하나요?

궁금합니다.

작성중인 코드―solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
function solution(jobs) {
    class Heap {
        constructor (compare) {
            this.compare = compare ? compare : (a, b) => a - b
            this.arr = []
        }

        top () {
            return this.arr[0]
        }

        size () {
            return this.arr.length
        }

        push (val) {
            const tail = this.size()
            this.arr[tail] = val
            this._reheapUp(tail)
            return this.size()
        }

        pop () {
            const tail = this.size() - 1
            this._swap(0, tail)
            const val = this.arr.pop()
            this._reheapDown(0)
            return val
        }

        _swap (indexA, indexB) {
            const temp = this.arr[indexA]
            this.arr[indexA] = this.arr[indexB]
            this.arr[indexB] = temp
        }

        _reheapUp (index) {
            if (index > 0) {
                const parent = parseInt((index - 1) / 2, 10)
                if (this.compare(this.arr[parent], this.arr[index]) > 0) {
                    this._swap(parent, index)
                    this._reheapUp(parent)
                }
            }
        }

        _reheapDown (index) {
            const left = index * 2 + 1
            const right = index * 2 + 2

            if (left < this.size()) {
                const child = right < this.size() && this.compare(this.arr[left], this.arr[right]) > 0 ?
                      right : left
                if (this.compare(this.arr[index], this.arr[child]) > 0) {
                    this._swap(child, index)
                    this._reheapDown(child)
                }
            }
        }
    }

    const done = []
    let runtime = 0

    // jobs.sort((a, b) => a[0] - b[0])

    const heap = new Heap((job1, job2) => {
        return job1[1] - job2[1]
    })

    function run () {
        console.log(heap.arr)
        while (heap.size()) {
            const process = heap.pop()
            if (runtime < process[0]) runtime = process[0]
            runtime += process[1]
            const taken = runtime - process[0]
            done.push(taken)
        }
        console.log(runtime)
    }

    for (let i = 0; i < jobs.length; i++) {
        const job = jobs[i]
        if (job[0] <= runtime) {
            heap.push(job)
        } else {
            run()
            heap.push(job)
        }
    }
    run()

    return parseInt(done.reduce((acc, cur) => {
        return acc + cur
    }, 0) / done.length, 10)
}
1 개의 답변
bongjinpark1

자문자답합니다.
유휴시간중, 같은 시간에 들어온 요청끼리는 인덱스 순이 아니라, 작업시간이 적은순으로 작업에 들어가야합니다. (최적해 구할때처럼)

그밖에, 엉뚱한 부분에서 한참 해멨네요.
주의하실점은 작업 하나가 끝날때마다 나머지 작업들의 우선순위를 재계산해야된다는 점입니다.
도움되는 테스트 케이스 첨부합니다.
입력: [[0, 3], [1, 9], [2, 6], [4, 3]]
출력: 9
작업순서 [0, 3], [2, 6], [4, 3], [1, 9]

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.