Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

rmyak's blog

By rmyak, history, 4 weeks ago, In English,

I came across this problem in leetcode posted by one of the users as interview question.Need help in solving this problem.


You are given a list of jobs, each with a deadline, and requires a certain amount of time to be completed.

Each worker can perform 1 job at a time. What is the minimum number of workers required to be able to complete all jobs within the deadline?

Deadlines are listed in terms of days after the start. A job with deadline of 1 and duration of 1 means that this job is due on Day 1 and requires 1 day to complete.

Example:

deadlines = [3, 2, 3] durations = [2, 1, 1] Answer: 2 Explanation: Use 1 worker for jobs 1 and 2, Use another worker for job 3.


Help needed in solving this problem. Is it a NP hard bin packing problem or are there any other approaches.

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it