Weighted Job Scheduling Medium 0 attempts
GeeksforGeeks ↗

Weighted Job Scheduling

Medium Dynamic ProgrammingMemoization GeeksforGeeks

You're given a list of jobs, each with a start time, an end time, and a profit. Choose a subset of jobs whose time intervals don't overlap with one another so that the total profit earned is as large as possible.

Input Format
Implement maxProfit(jobs). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
jobs = [[1,2,50],[3,5,20],[6,19,100],[2,100,200]]
Output
250

Example 2

Input
jobs = [[1,2,5]]
Output
5
Constraints
  • 1 <= N <= 10^5
  • 1 <= start[i] < end[i] <= 10^9
  • 1 <= profit[i] <= 10^4
Test Cases (2)
Case 1
Args: [[[1,2,50],[3,5,20],[6,19,100],[2,100,200]]] Expected: 250
Case 2
Args: [[[1,2,5]]] Expected: 5
Topics
Dynamic ProgrammingMemoization

DP + Binary Search

javascript
function maxProfit(jobs) {
  jobs.sort((a,b)=>a[1]-b[1]);
  const n = jobs.length, dp = Array(n).fill(0);
  dp[0] = jobs[0][2];
  function findLast(i) {
    let lo=0, hi=i-1, res=-1;
    while (lo<=hi) {
      const mid=(lo+hi)>>1;
      if (jobs[mid][1]<=jobs[i][0]) { res=mid; lo=mid+1; } else hi=mid-1;
    }
    return res;
  }
  for (let i=1;i<n;i++) {
    let incl = jobs[i][2];
    const l = findLast(i);
    if (l!==-1) incl += dp[l];
    dp[i] = Math.max(dp[i-1], incl);
  }
  return dp[n-1];
}

Time: O(n log n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript