Deviopath › TypeScript

Weighted Job Scheduling

Hard · Algorithms

Each Job runs from start to end and pays profit. Two jobs can both be taken if one ends at or before the moment the other starts (a.end <= b.start).

Write maxProfit(jobs) that returns the largest total profit of a set of non-overlapping jobs (0 for no jobs).

Hint: sort by end time and use dynamic programming; for each job, find the last job that ends before it starts (binary search).

Next: Diff Two Objects