मान लीजिए हमारे पास अलग-अलग समय आवश्यकताओं वाले कार्यों की एक सरणी है, k अलग-अलग व्यक्ति हैं जिन्हें कार्य सौंपे जाने हैं और हमारे पास यह भी है कि एक असाइनी को कार्य की एक इकाई करने में कितना समय t लगता है। हमें निम्नलिखित प्रतिबंधों के साथ सभी कार्यों को पूरा करने का न्यूनतम समय ढूंढना है।
एक असाइनी को केवल सन्निकट कार्य सौंपे जा सकते हैं।
दो असाइनी एक ही कार्य को साझा या निष्पादित नहीं कर सकते।
तो, यदि इनपुट k = 4, t = 5, job = {12, 6, 9, 15, 5, 9} की तरह है, तो आउटपुट 75 होगा क्योंकि हमें यह समय [12], [6, 9], [15] और [5, 9] असाइन करके मिलता है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
एक फ़ंक्शन is_valid() परिभाषित करें। यह time, K, job लेगा
n := job का आकार
count := 1, curr_time := 0, i := 0
जब i < n, करें
यदि curr_time + job[i] > time, तो
curr_time := 0
count := count + 1
अन्यथा,
curr_time := curr_time + job[i]
i := i + 1
count <= K होने पर true वापस करें
मुख्य विधि से, निम्नलिखित करें <
n := job का आकार
end := 0, begin := 0
i के लिए 0 से n की सीमा में, करें
end := end + job[i]
res := end
job_max := job का अधिकतम
जब begin <= end, करें
mid := ((begin + end) / 2) पूर्णांक भाग लें
यदि mid >= job_max और is_valid(mid, K, job) true है, तो
res := res, mid का न्यूनतम
end := mid - 1
अन्यथा,
begin := mid + 1
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 = 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
