Weighted Job Scheduling Medium 0 attempts
GeeksforGeeks ↗

Weighted Job Scheduling

Medium Dynamic ProgrammingMemoization GeeksforGeeks

Given jobs with start, end times and profits, find maximum profit subset of non-overlapping jobs.

Example: jobs: (1,2,50),(3,5,20),(6,19,100),(2,100,200) → Output: 250

Sample Input
—
Sample Output
—
Constraints
  • 1 <= N <= 10^5
  • 1 <= start[i] < end[i] <= 10^9
  • 1 <= profit[i] <= 10^4
Topics
Dynamic ProgrammingMemoization

DP + Binary Search

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