1352. Maximum Profit In Job Scheduling¶

Difficulty: Hard

1352. Maximum Profit in Job Scheduling

Hard

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⁴

Solution¶

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

class Solution {
    static class Tuple {
        int start, end, profit;
        public Tuple(int start, int end, int profit) {
            this.start = start;
            this.end = end;
            this.profit = profit;
        }
        @Override
        public String toString() {
            return "Tuple{" +
                   "start=" + start +
                   ", end=" + end +
                   ", profit=" + profit +
                   '}';
        }
    }
    static class customSort implements Comparator<Tuple> {
        @Override
        public int compare(Tuple first, Tuple second) {
            int op1 = Integer.compare(first.start, second.start);
            if (op1 != 0)
                return op1;
            return Integer.compare(first.end, second.end);
        }
    }
    private ArrayList<Tuple> arr;
    private int dp[];
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        arr = new ArrayList<>();
        for (int i = 0; i < n; i++)
            arr.add(new Tuple(startTime[i], endTime[i], profit[i]));
        Collections.sort(arr, new customSort());
        dp = new int[n + 1];
        Arrays.fill(dp, -1);
        return solve(0);
    }
    private int solve(int ind) {
        if (ind >= arr.size())
            return 0;
        if (dp[ind] != -1)
            return dp[ind];

        int low = ind + 1, high = arr.size() - 1, next = arr.size();
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr.get(mid).start >= arr.get(ind).end) {
                next = mid;
                high = mid - 1;
            } else
                low = mid + 1;
        }

        int op1 = solve(ind + 1);
        int op2 = arr.get(ind).profit + solve(next);

        return dp[ind] = Math.max(op1, op2);
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here