[Grind75-LeetCode] Maximum Profit in Job Scheduling JAVA

반응형

728x90

[Grind75-LeetCode] Maximum Profit in Job Scheduling - Hard

---

접근

• dp
• 이진 탐색

---

풀이

Job 스케줄러를 통해 얻을 수 있는 최대 이득을 구하는 문제이다. 시작 시간이 들어있는 배열, 종료 시간이 들어있는 배열 그리고 이익 값이 들어있는 배열이 주어진다. Job은 비선점 방식으로 수행이 되며 어떤 작업이 끝나는 시간에 다른 작업을 시작할 수 있다.

 

각 작업의 시간과 이득을 객체로 합쳐 놓고 종료시간을 기준으로 정렬한 뒤 dp와 이진 탐색을 통해 풀면 된다. 풀었던 방법과 성능이 제일 좋았던 코드는 알고리즘 자체는 동일하고 리스트를 사용하냐 배열을 사용하냐 정도의 차이였기 때문에 성능이 제일 좋았던 배열을 사용한 코드를 바로 들고 왔다.

    class Job {
        int start, end, profit;

        public Job(int start, int end, int profit) {
            this.start = start;
            this.end = end;
            this.profit = profit;
        }
    }

각 시간과 이익을 담는 클래스이다.

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int len = profit.length;
        Job[] jobs = new Job[len];

        for (int i = 0; i < len; i++) {
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }
        Arrays.sort(jobs, (a, b) -> Integer.compare(a.end, b.end));

 구현부로 각 배열의 값들을 객체로 만들어 담아준 뒤 종료 시간을 기준으로 정렬한다. 

	int[] dp = new int[len];
        dp[0] = jobs[0].profit;

        for (int i = 1; i < len; i++) {
            int start = jobs[i].start;
            int left = 0, right = i - 1, res = -1;
            
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (jobs[mid].end <= start) {
                    res = mid;
                    left = mid + 1;
                } else
                    right = mid - 1;
            }

dp와 이진 탐색 부분이다. 이진 탐색을 통해 작업을 찾게 되는데 탐색의 범위는 현재 작업의 전까지를 범위로 두고 탐색하게 된다. 그리고 현재 작업의 시작 시간보다 작은 종료 시간을 찾는데 그중 제일 큰 값을 찾는다. 

	    int take = jobs[i].profit;
            if (res != -1)
                take += dp[res];
            dp[i] = Math.max(take, dp[i - 1]);
        }
        return dp[len - 1];
    }

현재 작업의 이익에 현재 작업 전에 수행할 수 있는 가장 큰 작업의 이익을 더하여 현재까지 구해졌던 최대 이익과 비교해 dp배열을 최신화하게 된다.

---

전체 코드

class Solution {
    class Job {
        int start, end, profit;

        public Job(int start, int end, int profit) {
            this.start = start;
            this.end = end;
            this.profit = profit;
        }
    }

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int len = profit.length;
        Job[] jobs = new Job[len];

        for (int i = 0; i < len; i++) {
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }
        Arrays.sort(jobs, (a, b) -> Integer.compare(a.end, b.end));

        int[] dp = new int[len];
        dp[0] = jobs[0].profit;

        for (int i = 1; i < len; i++) {
            int start = jobs[i].start;
            int left = 0, right = i - 1, res = -1;

            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (jobs[mid].end <= start) {
                    res = mid;
                    left = mid + 1;
                } else
                    right = mid - 1;
            }

            int take = jobs[i].profit;
            if (res != -1)
                take += dp[res];
            dp[i] = Math.max(take, dp[i - 1]);
        }
        return dp[len - 1];
    }
}