[Algorithm] Job Scheduling - Javascript

[LeetCode 1235번]

Maximum Profit in Job Scheduling - LeetCode

 

1. 문제

startTime과 endTime이 정해져 있는 작업 데이터로, 최대 profit을 만들 수 있는 작업의 조합을 찾는 문제이다.

LeetCode 1235번 문제

LeetCode 1235번 Example 2

 

 

2. 해결

  Job Scheduling은 DFS를 통해 완전 탐색으로 풀 수는 있겠지만, 문제의 조건에 따라 오버플로우가 발생할 수 있다.

우리는 DP와 이진 탐색을 활용하여 O(N log N)으로 해결할 것이다.

 

[문제 해결의 핵심 포인트]

  DP는 더 큰 값을 계속해서 누적해가기 위함이다. 이 때, jobs 배열은 다음 작업이 현재 작업보다 이후에 시작되는 것을 보장해야하기 때문에 startTime 순으로 정렬해야 한다.

 

dp는 index가 큰 값부터 작은 값으로 내려가면서 누적한다. (반대로도 가능은 함)

dp[i] = Math.max(dp[i+1], jobs[i].profit + dp[next])

next는 현재 작업 다음에 연결되어 작업 가능한 job의 index를 의미한다.

즉, 현재 작업의 endTime보다 next 작업의 startTIme이 작거나 같아야한다.

 

아래의 그림에서 index가 2 인 작업을 선택한다면, index가 3, 4인 작업들은 수행할 수 없으므로,

dp[2] = Math.max(dp[3], 100+dp[5])가 되고 (dp[5]는 마지막 0 값임)

이는 index 2 작업과 index 3 + index 4 작업 중 더 큰 profit 값을 dp[2]에 기록하는 것을 의미한다. (문제 해결의 본질)

 

이렇게 최대를 누적하며 index 0의 값을 반환하면 원하는 최대 profit을 얻을 수 있다.

 

3. Javascript 코드

/**
 * @param {number[]} startTime
 * @param {number[]} endTime
 * @param {number[]} profit
 * @return {number}
 */
var jobScheduling = function(startTime, endTime, profit) {
    const jobs = profit.map((profitValue,i)=>({start:startTime[i], end:endTime[i], profit:profitValue}));
    const dp = new Array(jobs.length+1).fill(0); 
    
    const searchNextJob = (idx) => {
        let low = idx+1, high = jobs.length, mid;
        while(low < high) {
            mid = Math.floor((low + high)/2);
            if(jobs[mid].start >= jobs[idx].end) high = mid;
            else low = mid + 1;
        }
        return low;
    }
    
    jobs.sort((a,b)=>a.start-b.start);
    
    for(let i=jobs.length-1; i>=0; i--){
        const next = searchNextJob(i);      
        dp[i] = Math.max(dp[i+1], jobs[i].profit+dp[next]);
    }
    
    return dp[0];
};