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

Cho mảng công việc với thời gian yêu cầu khác nhau, k người phân công, và thời gian t mà một người làm 1 đơn vị việc. Tìm thời gian tối thiểu hoàn thành tất cả công việc với ràng buộc: người làm chỉ được nhận việc liên tiếp, và hai người không chia sẻ một việc.

Ví dụ: k = 4, t = 5, job = [12, 6, 9, 15, 5, 9] → Kết quả: 75 (phân chia: [12], [6,9], [15], [5,9]).

Thuật toán (Binary Search trên đáp án)

1. Hàm is_valid(time, K, job): kiểm tra có thể phân chia công việc trong time không. Duyệt job, gom nhóm liên tiếp sao cho tổng ≤ time, đếm số nhóm. Trả về True nếu số nhóm ≤ K.
2. Binary search trên khoảng [max(job), sum(job)] tìm time nhỏ nhất thỏa mãn is_valid.
3. Kết quả = time_tối_thiểu × T.

Ví dụ code

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 = sum(job)
    begin = 0
    res = end
    job_max = max(job)
    while begin <= end:
        mid = (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))

Input

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

Output

75