medium

Job Sequencing with Deadlines

Each job takes one unit of time and has a deadline and a profit; profit is earned only if the job is finished by its deadline. Only one job can run at a time. Choose and order jobs to maximise total profit.

Constraints
  • 1 ≤ n ≤ 10^5
  • 1 ≤ deadline[i] ≤ n
  • 1 ≤ profit[i] ≤ 10^9
Examples
in: jobs = [(deadline 2, profit 100), (1, 19), (2, 27), (1, 25), (3, 15)]
out: 142
Schedule profits 25, 100, 15 in slots 1, 2, 3.

Code it yourself

Solve in
Test execution is not yet available for this exercise.Practice journal →Draft saved in this browser.
Hints:
Which approach applies?

Choose an approach to check your pattern recognition, or reveal the discussion when you need help.