11. Maximum Profit in Job Scheduling{IMP}

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

Solution: (DP)

Sort array with starting time and calculate maximum profit with non overlapping intervals

class Solution
{
public:
    int jobScheduling(vector<int> &startTime, vector<int> &endTime, vector<int> &profit)
    {

        int n = startTime.size();

        vector<pair<int, pair<int, int>>> v;
        vector<int> dp;

        for (int i = 0; i < n; i++)
        {
            v.push_back({startTime[i], {endTime[i], profit[i]}});
        }

        sort(v.begin(), v.end());

        for (int i = 0; i < v.size(); i++)
        {
            dp.push_back(v[i].second.second);
        }

        int j = 1;

        while (j < n)
        {
            int i = 0;
            int st = v[j].first;
            int et = v[j].second.first;
            for (int i = 0; i < j; i++)
            {
                if (st < v[i].second.first)
                {
                    continue;
                }
                else
                {
                    dp[j] = max(dp[j], dp[i] + v[j].second.second);
                }
            }
            j++;
        }

        int maxProfit = INT_MIN;
        for (int i = 0; i < dp.size(); i++)
        {
            if (dp[i] > maxProfit)
            {
                maxProfit = dp[i];
            }
        }

        return maxProfit;
    }
};

Time Complexity: O(n^2)

Approach

For each time point, we can store the maximum profit we can get starting from that time. We can calculate the maximum profit for the start time using the max profits for the job's end time.

image

Algorithm: Sort the array on starting time Iterate from back and find the calculate the max profit for the ending time Store in a map to access in O(1) time

Solution

class Solution
{
public:
    static bool comparator(vector<int> &a, vector<int> &b)
    {
        return a[0] > b[0];
    }

    int jobScheduling(vector<int> &startTime, vector<int> &endTime, vector<int> &profit)
    {

        vector<vector<int>> v;
        map<int, int> dp;

        for (int i = 0; i < startTime.size(); i++)
        {
            v.push_back({startTime[i], endTime[i], profit[i]});
        }

        sort(v.begin(), v.end(), comparator);
        
        int maxProfit = 0;
        for (int i = 0; i < v.size(); i++)
        {
            int p = v[i][2];
            auto itr = dp.lower_bound(v[i][1]);
            int prevP = (itr != dp.end()) ? itr->second : 0;

            maxProfit = max(maxProfit, p + prevP);
            dp[v[i][0]] = maxProfit;
        }

        return maxProfit;
    }
};

Time Complexity: O(n log n)