[leetcode #1235] Maximum Profit in Job Scheduling

Problem

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

Constraints:

・ 1 <= startTime.length == endTime.length == profit.length <= 5 * 10⁴
・ 1 <= startTime[i] < endTime[i] <= 10⁹
・ 1 <= profit[i] <= 10⁴

Idea

풀었는데 Time Limit Exceeded나서 다른 사람 풀이를 봤다 ㅜㅜ 아, 이러면 푼 게 아니게 되는건가.

처음에는 endTime을 기준으로 정렬을 한 뒤 역순으로 탐색하면서 treeMap에 startTime을 기준으로 profit max값을 넣었다. 어디서 잘못되었는지 정확히 모르겠지만 treeMap에 최대값을 저장할 때 이미 지난 key들에 현재 바뀐 값이 반영이 되지 않는 문제가 있었다. 예를 들면 key값이 10일 때 11 이상이 되는 key값들도 반영되어야 하지만 그렇게 하지 못해 treeMap을 역탐색하여 값을 바꿔준 것이다. O(n²)으로 풀었으니 Time Limit Exceeded가 발생할 수밖에 없었다.

답을 보니 역순으로 풀지 않고 순차적으로 풀었다. 물론 역순으로 해도 정상적인 알고리즘이라면 Time Limit 안 걸리고 풀었어야 하지만 내 알고리즘에 문제가 있었다는 걸 부인할 수 없다.

알고리즘은 다음과 같다.

1. startTime, endTime, profit을 저장하는 2d array를 생성한다.
2. 2d array를 endTime을 기준으로 정렬한다.
3. 정렬한 2d array를 탐색한다.
   a. startTime의 floor가 되는 key값이 있으면 해당 entry의 value를 가지고 온다. 이 때 가지고 오는 값은 startTime 이전에 끝난 job의 max profit이다.
   b. 현재 job의 profit과 startTime 이전에 끝난 job들의 max profit을 더한다.
   c. 이 때 더한 값이 max보다 크면 max값을 바꿔주고, treeMap에 endTime을 key로 하여 max값을 저장한다.
4. max를 리턴한다.

거의 다 풀었는데 Time Limit Exceeded 걸렸을 때만큼 안타까운 일이 있을까 ㅜㅜ

Solution

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
    	int n = startTime.length;
    	TreeMap<Integer, Integer> treeMap = new TreeMap<>();
    	int[][] dp = new int[n][3];
    	for (int i=0; i < n; i++) {
            dp[i][0] = startTime[i];
            dp[i][1] = endTime[i];
            dp[i][2] = profit[i];
        }

        Arrays.sort(dp, (a,b) -> a[1] - b[1]);
        treeMap.put(0, 0);
        int max = 0;

        for (int[] job : dp) {
            int start = job[0];
            int prevProfit = treeMap.floorEntry(start).getValue();
            if (job[2] + prevProfit > max) {
                max = job[2] + prevProfit;
                treeMap.put(job[1], max);
            }
        }

        return max;
    }
}

Reference

https://leetcode.com/problems/maximum-profit-in-job-scheduling/