[문제 이름 : Maximum Profit In Job Scheduling (리트코드, Hard) ]
문제 url : https://leetcode.com/problems/maximum-profit-in-job-scheduling
내가 작성한 코드는 아래와 같다.
import java.util.*;
class Solution {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int jobLen = profit.length;
int[][] jobs = new int[jobLen][3];
for(int i=0; i<jobLen; i++) {
jobs[i][0] = startTime[i];
jobs[i][1] = endTime[i];
jobs[i][2] = profit[i];
}
// 끝나는 시간에 대하여 오름차순 정렬
Arrays.sort(jobs, (a,b) -> a[1] - b[1]);
// dp[i] => i번째 작업까지의 최대 이익 저장
// i-1에서 i번째 작업을 포함하는 것과 비교
int[] dp = new int[jobLen];
dp[0] = jobs[0][2];
for(int i=1; i<jobLen; i++) {
int currentProfit = jobs[i][2];
int searchProfit = binarySearch(jobs, i);
if(searchProfit >= 0) {
currentProfit += dp[searchProfit];
}
dp[i] = Math.max(dp[i-1], currentProfit);
}
return dp[jobLen-1];
}
// 현재 작업과 겹치지 않는 제일 마지막 작업을 탐색한다.
static int binarySearch(int[][] jobs, int index) {
int start = 0;
int end = index-1;
while(start <= end) {
int mid = (start + end) / 2;
if(jobs[mid][1] <= jobs[index][0]) {
start = mid+1;
} else {
end = mid-1;
}
}
return start-1;
}
}
[풀이 과정]
1. 2차원 배열을 생성하여, 작업의 시작시간, 종료시간, 수익 정보를 저장한다. 이후, 각 작업에 대하여 종료 시간에 대해 정렬한다.
2. DP(Dynamic Programming)를 사용한다. 배열을 선언하는데, 이때 dp[i]는 i번째 작업을 고려했을 떄 얻을 수 있는 최대 수익을 의미한다.
3. binarySearch에서, 계속 순환을 하며 특정 작업의 종료시간보다 현재 작업의 시작시간이 크거나 같으면, 더 큰 시작 시간으로 테스트 하고, 아니라면 더 작은 종료시간에서 while문을 돌며 탐색을 계속한다.
4. index에 해당하는 작업과 겹치지 않는 제일 마지막 시작 시간을 반환한다. start-1이 배열의 범위를 벗어날 수 있으므로, 0 이상인 경우에만 현재 수익에 합산한 후, 이를 dp값 갱신 시 체크해준다.
풀이 시간 : 1시간 15분