1235. Maximum Profit in Job Scheduling

1235. Maximum Profit in Job Scheduling

Problem Solving - Day 56

ยท

7 min read

Hello, reader ๐Ÿ‘‹๐Ÿฝ ! Welcome to day 56 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 1235. Maximum Profit in Job Scheduling.


๐Ÿค” Problem Statement

  • There are n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].
  • Given the startTime, endTime and profit arrays, return the maximum profit from all the jobs such that there are no two jobs in the subset with overlapping time range.
  • If a job ends at time X, another job starting at time X can be selected.
  • E.g.:
    • startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70] => 120

๐Ÿ’ฌ Thought Process - Dynamic Programming (Memoization)

  • On careful observation, we have two choices for any job at index i -> either include the job or exclude it.
  • If we include the current job at index i, then we can only choose the next job that starts after this job ends.
  • So in the end, the jobs that need to be scheduled depends on the start time, which in turn depends on the end time of the previously executed job.
  • Since the given jobs' start, end time are not sorted in ascending order, we could have inputs like this: startTime = [3,2,1,3]. But the startTime of the next job should be greater than the end time of the current job.
  • So we would have to sort our array according to the start time to ensure that we consider all the jobs by their start time and the condition where startTime[i+1] >= endTime[i] holds true for every job.
  • We'll sort all the jobs by their start time and will save the start time, end time, and the profit.
  • So our jobs array would have a structure like this: jobs[n][3] where n = number of jobs. jobs[i][0] will have the startTime of job i, job[i][1] will have the endTime of job i, and jobs[i][2] will hold the profit for job i.
  • Once we sort the jobs, we can call a function that would take the current index of the job and the jobs array. There would be two choices at evert index like we already discussed: include or exclude the job.
  • Excluding the current job is pretty straightforward, we just recursively call the function again with index i+ 1.
  • But if we do include the current job, we will have to choose the next job to continue calling recursively.
  • The way we can do this is find the next job whose startTime >= endTime and since our array is sorted, we can make use of binary search to do this.
  • We will have a start and end pointers where start will begin from index i +1 and end would be n-1. Our nextIndex will initially be -1.
  • Whenever we find any job j whose jobs[j][0] >= jobs[i][1], we'll update our nextIndex to the current job index j.
  • And we continue this until our start <= end. At the end of the binary search iteration, we would have found the smallest nextIndex such that jobs[nextIndex][0] >= jobs[i][1].
  • Once we find the nextIndex, we can add the current job's profit with that returned by the recursive call for nextIndex.
  • Finally at the end of the current call, we return the maximum of the two cases: including the current job and excluding the current job.
  • Also if you observe, we'd need to memoize the maximum profit obtained at every job at index i that we calculate.
  • This is needed because, let's say our current index was 0.
    • Then we have two choices: include the current job or exclude the current job.
    • Let's assume that the next immediate job has a start time greater or equal to the end time of the current job.
    • In that case, we would be calling the same index twice (one for including current job and the other for excluding).
  • We can improve this and avoid making multiple calls for the same index by memoizing the values already calculated.

๐Ÿ‘ฉ๐Ÿฝโ€๐Ÿ’ป Solution - Dynamic Programming (Memoization)

  • Below is the code for the dynamic programming (memoization) approach.
class Solution {
    private int n;
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        n = startTime.length;
        int[] memo = new int[n];
        Arrays.fill(memo, -1);

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

        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);

        return jobSchedulingHelper(0, jobs, memo);
    }

    private int jobSchedulingHelper(int index, int[][] jobs, int[] memo) {
        if(index >= n) return 0;

        if(memo[index] != -1) return memo[index];

        int currStartTime = jobs[index][0];
        int currEndTime = jobs[index][1];
        int currProfit = jobs[index][2];

        // choose the next index
        int nextIndex = findNextIndex(index, jobs, currEndTime);

        int includeCurr = currProfit;
        if(nextIndex != -1) {
            includeCurr += jobSchedulingHelper(nextIndex, jobs, memo);
        }
        int excludeCurr = jobSchedulingHelper(index+1, jobs, memo);

        return memo[index] = Math.max(includeCurr, excludeCurr);
    }

    private int findNextIndex(int index, int[][] jobs, int endTime) {        
        int start = index + 1;
        int end = n-1;
        int nextIndex = -1;

        while(start <= end) {
            int mid = (start + end) / 2;
            int midStart = jobs[mid][0];

            if(midStart >= endTime) {
                nextIndex = mid;
                end = mid - 1;
            }
            else {
                start = mid + 1;
            }
        }

        return nextIndex;
    }
}

/*
- At every index, you can either choose or not choose the job
- If you choose the current index, add it and then start with next index such that next jobs' startTime >= current jobs' endTime
*/
Time Complexity: O(n log n)
  - n = length of the array
Space Complexity: O(n log n)
  - n = length of the array

๐Ÿ’ฌ Thought Process - Dynamic Programming (Tabulation)

  • We can also convert the above memoized solution to tabulation and avoid recursion stack space.
  • First, we'll keep the same 1D array to cache our results.
  • Then let's convert the recursive calls to loops. In the memoization approach, we started the call from index 0. Hence, in tabulation approach we'll do the opposite and start from index n-1 to 0.
  • At every index, we'll perform the same choices: include current job or exclude current job.
  • If we exclude the current job at index i, then the profit for this choice would be the profit we calculated at index i+1, which we can get from the cached results.
  • If we are at index n-1, then this choice will have 0 profit as there's no next job to choose from.
  • If we do choose the job at index i, then the profit for this choice would be the current job's profit + the profit calculated from the next job.
  • We can choose the next job using the same utility that runs the binary search to find the smallest job j such that, jobs[j][0] >= jobs[i][1].
  • Then we'll cache the current job's profit as the maximum of the two choices.
  • Finally once the iteration is done, we can return the cached profit at index 0, as this will contain all the profits from the jobs 1 to n-1.

๐Ÿ‘ฉ๐Ÿฝโ€๐Ÿ’ป Solution - Dynamic Programming (Tabulation)

  • Below is the code for the dynamic programming (tabulation) approach.

    class Solution {
      private int n;
      public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
          n = startTime.length;
          int[] dp = new int[n];
          int[][] jobs = new int[n][3];
    
          for(int i = 0; i<n; i++) {
              jobs[i][0] = startTime[i];
              jobs[i][1] = endTime[i];
              jobs[i][2] = profit[i];
          }
          Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
    
          for(int index = n-1; index >= 0; index--) {
              int currStartTime = jobs[index][0];
              int currEndTime = jobs[index][1];
              int currProfit = jobs[index][2];
    
              int nextIndex = findNextIndex(index, jobs, currEndTime);
              int includeCurr = currProfit;
              if(nextIndex != -1) {
                  includeCurr += dp[nextIndex];
              }
              int excludeCurr = (index == n-1) ? 0 : dp[index+1];
    
              dp[index] = Math.max(includeCurr, excludeCurr);
          }
    
          return dp[0];
      }
    
      private int findNextIndex(int index, int[][] jobs, int endTime) {        
          int start = index + 1;
          int end = n-1;
          int nextIndex = -1;
    
          while(start <= end) {
              int mid = (start + end) / 2;
              int midStart = jobs[mid][0];
    
              if(midStart >= endTime) {
                  nextIndex = mid;
                  end = mid - 1;
              }
              else {
                  start = mid + 1;
              }
          }
    
          return nextIndex;
      }
    }
    
  • You can find the link to the GitHub repo for this question here: 1235. Maximum Profit in Job Scheduling.


Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!