Tìm thời gian tối thiểu để hoàn thành tất cả các công việc với các ràng buộc nhất định trong Python

Giả sử chúng ta có một mảng công việc với các yêu cầu thời gian khác nhau, có k người khác nhau để giao việc và chúng ta cũng có bao nhiêu thời gian mà một người được giao mất để làm một đơn vị công việc. Chúng tôi phải tìm ra thời gian tối thiểu để hoàn thành tất cả các công việc với những ràng buộc sau.

• Người được giao chỉ có thể được giao các công việc liền kề.

• Hai người được giao không thể chia sẻ hoặc thực hiện một công việc duy nhất.

Vì vậy, nếu đầu vào là k =4, t =5, job ={12, 6, 9, 15, 5, 9}, thì đầu ra sẽ là 75 khi chúng ta nhận được lần này bằng cách gán [12], [6 , 9], [15] và [5, 9]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm is_valid (). Điều này sẽ mất thời gian, K, việc làm

• n:=quy mô công việc

• count:=1, curr_time:=0, i:=0

• trong khi tôi

  • nếu curr_time + job [i]> time thì

    • curr_time:=0

    • count:=count + 1

  • nếu không,

    • curr_time:=curr_time + job [i]

    • i:=i + 1

• trả về true khi đếm <=K

• Từ phương thức chính, hãy thực hiện như sau <

• n:=quy mô công việc

• end:=0, begin:=0

• đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

  • end:=end + job [i]

• res:=end

• job_max:=tối đa công việc

• trong khi bắt đầu <=end, thực hiện

  • mid:=((begin + end) / 2) lấy phần nguyên

  • nếu mid> =job_max và is_valid (mid, K, job) là true thì

    • res:=tối thiểu res, mid

    • end:=mid - 1

  • nếu không,

    • bắt đầu:=mid + 1

• trả về res * T

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def is_valid(time, K, job):
   n = len(job)
   count = 1
   curr_time = 0
   i = 0
   while i < n:
      if curr_time + job[i] > time:
         curr_time = 0
         count += 1
      else:
         curr_time += job[i]
         i += 1
   return count <= K
def get_minimum_time(K, T, job):
   n = len(job)
   end = 0
   begin = 0
   for i in range(n):
      end += job[i]
   res = end
   job_max = max(job)
   while begin <= end:
      mid = int((begin + end) / 2)
      if mid >= job_max and is_valid(mid, K, job):
         res = min(res, mid)
         end = mid - 1
      else:
         begin = mid + 1
   return res * T
job = [12, 6, 9, 15, 5, 9]
k = 4
T = 5
print(get_minimum_time(k, T, job))

Đầu vào

4, 5, [12, 6, 9, 15, 5, 9]

Đầu ra

75