Блог пользователя rmyak

Автор rmyak, история, 5 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится