Maximum Profit in Job Scheduling

Maximum Profit in Job Scheduling

문제 내용

주어진 Job List를 이용해서 가장 높은 Profits를 계산 하시오

 

접근 방법

질문을 Knapsack 으로 변경해도 문제가 동일하다.

가방에 최대한 많은 양의 물건을 담고자 한다. 

얼마의 무개까지 담을 수 있는가? 와 동일하다.

DP를 이용한 최대 Profits를 계산하면 된다.

문제가 [starttime, endtime, profit]으로 아래와 같이 주어졌다고 생각해 보겠다.

[1,3,20]

[2,5,20]

[3,10,100]

[4,6,70]

[6,9,60]

이런 문제가 있다고 했을 때 DP는 Profit을 확정짓는 endtime 기준으로 해당 시점의 최대 Profit을 유지하면 된다.

우선 endtime을 기준으로 주어진 문제를 Sorting 처리 하겠다.

[1,3,20]

[2,5,20]

[4,6,70]

[6,9,60]

[3,10,100]

그리고 DP는 모두 5개가 필요하다.

상기 그림처럼 endtime기준으로 산출 가능한 최대한의 Profits을 유지 하면 된다.

우선 DP의 첫번째 공간은 20이 된다.

이후 2번째 공간은 몇이 될까?

역시 20밖에는 될 수 없다. 2번째 Job이나 첫번재 Job이나 동일한 Profit이기 때문이다.

3번째 공간은 70을 위해서 만들어진 공간이다. 이 70의 Job Profit을 Sum하기 위해서는 3번째 Job의 Starttime과 다른 Job간의 시간상 겹침이 발생하면 안된다.

즉 2번재 Job의 endtime은 3번째 job의 starttime보다 높기 때문에 사용될 수 없다.

그래서 첫번째와 3번째 job Profit을 합쳐서 90이 나온다.

4번째는 60이다. 이 4번째 Job의 starttime과 70의 endtime이 정확히 동일함으로 연속된 job으로 사용가능하다.

그렇기 때문에 기존 DP되어있는 90과 자기자신 60을 더해서 150을 만들면 된다.

마지막으로 100을 갖고 있는 5번째 job이다. 이 5번째 job의 starttime은 3이다. endtime이 1,2,3으로 되어있는 job들 만이 대상으로 선정될 수 있다.

즉 첫번째 job을 제외하고는 아무 job도 활용이 되지 않는다.

$ 120 = 20 + 100 $ 이되는데, DP[4]가 $ 120 < 150 $ 더 크다.

가장 최고 값만을 유지 함으로 150이 된다.

이런식으로 알고리즘을 짜면 되는데, 한가지를 집고 넘어 가야한다. 현재 Job의 Starttime보다 작은 endtime은 어떻게 구할 것인가?

만약에 100개의 Job이 있고 101번째의 job의 starttime이 30이라고 할때 30보다 작은 endtime을 갖고 있는 마지막 DP는 몇번째인가?

가장 쉬운 방법은

왼쪽 부터 오른쪽으로 첫번재 20 profit의 endtime을 확인하고 이 endtime이 starttime보다 작은지 확인한다.

두번째 20 profit의 endtime을 확인하고 다시 한번더 오른쪽으로 간다.

90의 endtime이 30임을 확인하고, 4번째 150의 endtime이 30보다 높다는 것을 확인한다면,

3번째 DP 90이 101번째 job과 Profits를 Sum 할 수 있다는 것을 확인 할 수 있다.

이방식으로 하면 Search하는데 있어서 $ O(N) $ 시간이 걸린다.

이를 해결하기 위해서 Binary Search를 사용한다면 비약적으로 속도가 빨라질 수 있다.

상기 그림과 같이 mid를 확인하고 left +1그리고 right -1 을 하면서 $ O(\log_2 N) $ 으로 목표한 target을 찾아 내면 된다.

주의해야할 점은 mid+1을 확인해서 더이상 starttime보다 낮은 endtime이 없다는것을 확정해야 한다는 것이다.

var jobScheduling = function(startTime, endTime, profit) {

    var number = profit.length;
    var dp = new Array(number+1).fill(0); //end, profit
    var jobs = []; // start, end, profit
    jobs.push([0, 0, 0]);

    for(var i = 0; i<number;i++)
    {
        jobs.push([startTime[i], endTime[i], profit[i]]);
    }
    jobs.sort((a,b)=>a[1]-b[1]); // sort by start time

    for (let i = 1; i < dp.length; i++) {
        let start = jobs[i][0];
        let profit = jobs[i][2];

        //jobs[i]의 start는 이전 jobs의 end보다 크거나 같아야 한다. 그 pre index의 dp profit을 찾아야 한다.
        let right = i - 1;
        let left = 0;
        let mid = 0;

        while (left <= right) {
            // mid = left + Math.floor((right - left)/2);
            mid = (right + left) >> 1;

            if (jobs[mid][1] <= start) {
                if(jobs[mid+1][1] <= start){
                    left = mid + 1;
                } else {
                    break;
                }
            } else if (jobs[mid][1] > start) {
                right = mid - 1;
            }
        }

        //현재의 profit과 현재 start보다 이전 end를 갖고 있는 dp[] profit의 합이
        //이전 dp[i-1] 보다 크다면 현재의 dp[i]로 사용가능하지만 아니라면 지금 dp는 이전 dp를 계승한다
        dp[i] = Math.max(dp[i - 1], dp[mid] + profit);
        console.log(dp);
    }

    return dp[number];

};

 

시간복잡도는 Sorting을 처리함으로 $ O(NLogN) $ 이다.

한가지 주의 해야할 것이 있는데 mid를 찾을 때는 overflow를 방지 하기 위해서 하기 방식 중에 하나로 찾아야 한다.

mid = left + Math.floor((right - left)/2);
mid = (right + left) >> 1;