[leetcode][hard] Maximum Profit in Job Scheduling

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 * 104
• 1 <= startTime[i] < endTime[i] <= 109
• 1 <= profit[i] <= 104

 

profit 을 최대로 할 수 있는 job 들을 스케쥴링 하는 문제이다. 현재 시점에서 다음 job 들의 비용을 알 수 없기 때문에, 결국 가능성 있는 부분 문제들을 찾아보아야 한다.

 

나는 job object 를 만들어서 현재 index 에 해당하는 job 을 넣는경우와 안 넣는 경우 두가지의 경우로 나눠서 풀었다. 여기서 주의해야할 점은 현재 index 에 해당하는 job 을 넣는 경우에는 다음의 job 은 현재의 job 과 겹치면 안되기 때문에 겹치는 job 만큼 index 를 뛰어넘어줘야 한다는 점이다.

 

class Solution {
    static class Job {
		int startTime;
		int endTime;
		int profit;

		public Job(int startTime, int endTime, int profit) {
			this.startTime = startTime;
			this.endTime = endTime;
			this.profit = profit;
		}
	}

	public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
		int n = startTime.length;

		Job [] jobs = new Job[n];

		for (int i = 0; i < n; i++) {
			jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
		}

		Arrays.sort(jobs, Comparator.comparingInt(o -> o.startTime));

		Integer [] dp = new Integer[n];

		return solve(dp, jobs, 0);
	}

	private int solve(Integer[] dp, Job[] jobs, int i) {
		if (i >= jobs.length) {
			return 0;
		}

		if (dp[i] != null) {
			return dp[i];
		}

		Job cur = jobs[i];
		int next = jobs.length;

		for (int j = i+1; j < jobs.length; j++) {
			if (cur.endTime <= jobs[j].startTime) {
				next = j;
				break;
			}
		}


		// 현재 job 을 선택하는 경우
		int max = cur.profit + solve(dp, jobs, next);
		// 현재 job 을 선택하지 않는 경우
		max = Math.max(max, solve(dp, jobs, i+1));

		return dp[i] = max;
	}
}

 

위의 top down 방식으로 풀었는데, 이 로직의 시간복잡도는 $O(N^2)$ 이 된다. 아래 leetcode 솔루션 코드처럼 dp + binarySearch 를 조합함으로써 이 시간복잡도를 $O(NlogN)$ 으로 줄일 수 있다.

 

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) {
            jobs[i] = new int[] {startTime[i], endTime[i], profit[i]};
        }
        Arrays.sort(jobs, (a, b)->a[1] - b[1]);

				// job 의 starttime 은 1부터이므로 0의 값을 넣어두면 맨 처음 job 은 항상 이 값을 찾을 수 있다.
        TreeMap<Integer, Integer> dp = new TreeMap<>();
        dp.put(0, 0);
        for (int[] job : jobs) {
            int cur = dp.floorEntry(job[0]).getValue() + job[2];
            if (cur > dp.lastEntry().getValue())
                dp.put(job[1], cur);
        }
        return dp.lastEntry().getValue();
    }
}