Help required in solving a problem

Revision en1, by rmyak, 2020-01-21 21:30:31

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rmyak 2020-01-21 21:30:31 1063 Initial revision (published)