पायथन में दी गई बाधाओं के साथ सभी कार्यों को पूरा करने के लिए न्यूनतम समय खोजें

मान लीजिए कि हमारे पास अलग-अलग समय की आवश्यकताओं के साथ नौकरियों की एक सरणी है, नौकरी सौंपने के लिए k अलग-अलग व्यक्ति हैं और हमारे पास यह भी है कि एक असाइनी को नौकरी की एक इकाई को पूरा करने में कितना समय लगता है। हमें निम्न बाधाओं के साथ सभी कार्यों को पूरा करने के लिए न्यूनतम समय निकालना होगा।

• एक समनुदेशिती को केवल सन्निहित कार्य सौंपा जा सकता है।

• दो असाइनी एक ही कार्य को साझा या निष्पादित नहीं कर सकते हैं।

इसलिए, यदि इनपुट k =4, t =5, जॉब ={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 + job[i]

    • मैं :=मैं + 1

• गिनती <=K

  . होने पर सही लौटें

• मुख्य विधि से, निम्न कार्य करें

• n :=कार्य का आकार

• अंत:=0, प्रारंभ करें:=0

• मेरे लिए 0 से n की सीमा में, करें

  • अंत:=अंत + नौकरी [i]

• रेस :=अंत

• job_max :=अधिकतम नौकरी

• प्रारंभ करते समय <=अंत, करें

  • मध्य :=((शुरू + अंत) / 2) पूर्णांक भाग लें

  • अगर मध्य>=job_max और is_valid(mid, K, job) सही है, तो

    • रेस :=न्यूनतम रेस, मध्य

    • अंत:=मध्य - 1

  • अन्यथा,

    • प्रारंभ:=मध्य + 1

• रिटर्न रेस * टी

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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

इनपुट

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

आउटपुट

75