디스크 컨트롤러

문제 링크

문제 요약

• 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다.
• 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다.
• 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

제한사항

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

Input

• 각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs

output

• 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return

  • (단, 소수점 이하의 수는 버립니다)

해결방법

• 탐욕법

  • 전체의 평균을 줄여야한다.
  • 평균을 줄이려면 생성된 시간과 무관하게 작업의 수를 줄이는게 급선무이므로 가장 소요시간이 적은 작업부터 처리한다.

function solution(jobs) {
  let _jobs = jobs.slice(0).map((j, idx) => {
    return { id: idx, start: j[0], cost: j[1] }
  })

  let sum = 0

  for (let i = 0; _jobs.length; ) {
    const ableJobs = _jobs
      .filter(j => {
        return j.start <= i
      })
      .sort((a, b) => a.cost - b.cost)

    if (ableJobs.length) {
      const currentJob = ableJobs.shift()
      _jobs = _jobs.filter(job => job.id !== currentJob.id)
      i += currentJob.cost
      sum += i - currentJob.start
    } else {
      i++
    }
  }
  return Math.floor(sum / jobs.length)
}