পাইথনে প্রদত্ত সীমাবদ্ধতার সাথে সমস্ত কাজ শেষ করার জন্য সর্বনিম্ন সময় খুঁজুন

ধরুন আমাদের কাছে বিভিন্ন সময়ের প্রয়োজনীয়তার সাথে কাজের একটি অ্যারে আছে, সেখানে কাজ দেওয়ার জন্য k বিভিন্ন ব্যক্তি রয়েছে এবং আমাদের কাছেও আছে একজন অ্যাসাইনীর কাজের একটি ইউনিট করতে কতটা সময় লাগে। নিম্নলিখিত সীমাবদ্ধতার সাথে সমস্ত কাজ সম্পূর্ণ করার জন্য আমাদের সর্বনিম্ন সময় খুঁজে বের করতে হবে।

• একজন অর্পণকারীকে শুধুমাত্র সংলগ্ন কাজগুলি বরাদ্দ করা যেতে পারে৷

  ৷

• দুই অ্যাসাইনি একটি কাজ ভাগ বা সম্পাদন করতে পারে না।

সুতরাং, যদি ইনপুটটি k =4, t =5, job ={12, 6, 9, 15, 5, 9} এর মত হয়, তাহলে আউটপুট হবে 75 যেভাবে আমরা এই সময়টি [12], [6] অ্যাসাইন করে পাই। , 9], [15] এবং [5, 9]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন is_valid() সংজ্ঞায়িত করুন। এতে সময় লাগবে, কে, কাজ

• n :=কাজের আকার

• গণনা :=1, curr_time :=0, i :=0

• যখন আমি

  • যদি curr_time + job[i]> time, তাহলে

    • curr_time :=0

    • গণনা :=গণনা + 1

  • অন্যথায়,

    • curr_time :=curr_time + চাকরি[i]

    • i :=i + 1

• গণনা <=K

  হলে true ফেরত দিন

• মূল পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন <

• n :=কাজের আকার

• শেষ :=0, শুরু :=0

• 0 থেকে n রেঞ্জের জন্য, করুন

  • end :=end + job[i]

• res :=শেষ

• job_max :=চাকরির সর্বোচ্চ

• শুরু করার সময় <=শেষ করুন, করুন

  • mid :=((শুরু + শেষ) / 2) পূর্ণসংখ্যা অংশ নিন

  • যদি mid>=job_max এবং is_valid(mid, K, job) সত্য হয়, তাহলে

    • res :=ন্যূনতম রেস, মাঝামাঝি

    • শেষ :=মধ্য - 1

  • অন্যথায়,

    • শুরু :=মধ্য + 1

• রিটার্ন রিটার্ন * T

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def is_valid(time, K, job):n =len(job) count =1 curr_time =0 i =0 যখন i  সময়:curr_time =0 গণনা +=1 else:curr_time +=job[i] i +=1 রিটার্ন কাউন্ট <=Kdef get_minimum_time(K, T, job):n =len(job) end =0 begin =0 i এর range(n):end +=job[i] res =end job_max =max(job) while begin <=end:mid =int((begin + end) / 2) যদি mid>=job_max এবং is_valid(mid, K, job):res =min( res, mid) শেষ =mid - 1 else:begin =mid + 1 রিটার্ন res * Tjob =[12, 6, 9, 15, 5, 9]k =4T =5print(get_minimum_time(k, T, job)) 
ইনপুট
 
4, 5, [12, 6, 9, 15, 5, 9]
 
আউটপুট
 
75