পাইথনে দেওয়া সীমাবদ্ধতায় সব কাজ শেষ করার ন্যূনতম সময় বের করা

ধরা যাক বিভিন্ন সময় আওতাধীন কাজের একটি অ্যারে আছে, k জন ব্যক্তি কাজ বাঁটতে পারেন এবং প্রতিটি ব্যক্তি এক ইউনিট কাজ করতে t সময় নেয়। আমাদের সব কাজ শেষ করার ন্যূনতম সময় বের করতে হবে নিচের সীমাবদ্ধতা মেনে:

একজন ব্যক্তির শুধু সঙ্কলিত (contiguous) কাজ দেওয়া যায়।
দুইজন ব্যক্তি একই কাজ শেয়ার বা করতে পারবেন না।

যেমন, k=4, t=5, job=[12,6,9,15,5,9] হলে আউটপুট 75, কারণ কাজ বাঁট: [12], [6,9], [15], [5,9]।

সমাধানের ধাপসমূহ

is_valid(time, K, job) ফাংশন: দেওয়া time-এ K জন দিয়ে কাজ শেষ করা সম্ভব কিনা চেক করুন।
বাইনারি সার্চ ব্যবহার করে ন্যূনতম time বের করুন।
ফলাফল হলো res * T।

উদাহরণ

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))

ইনপুট

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