मान लीजिए कि हमारे पास पूर्णांकों की एक सूची है, जिन्हें कार्य कहा जाता है, जहां प्रत्येक आइटम एक अलग कार्य प्रकार का प्रतिनिधित्व करता है, हमारे पास एक गैर-ऋणात्मक पूर्णांक भी है, जैसे k। प्रत्येक कार्य को पूरा करने में एक इकाई समय लगता है और कार्यों को सही क्रम में पूरा किया जाना चाहिए, लेकिन हमारे पास दो समान प्रकार के कार्यों को करने के बीच k इकाई समय होना चाहिए। हम किसी भी समय कोई कार्य कर सकते हैं या प्रतीक्षा कर सकते हैं। हमें सभी कार्यों को पूरा करने में लगने वाले समय का पता लगाना होगा।
इसलिए, यदि इनपुट कार्यों की तरह है =[0, 1, 1, 2] k =2, तो आउटपुट 6 होगा, क्योंकि पहले दो कार्य अलग-अलग प्रकार के होते हैं, इसलिए उन्हें बिना किसी अंतराल के निष्पादित किया जा सकता है, अब समय पर 2, अगला कार्य उसी प्रकार का कार्य है जिसके लिए हमें 2-समय के स्लॉट की प्रतीक्षा करनी है, फिर कार्य करना है और अंत में अन्य प्रकार का कार्य करना है, टाइप 2। तो यह कार्य करें। तो यह [0, 1, रुको, रुको, 1, 2] जैसा है। इससे हम पहचान सकते हैं, हमें 6 टाइम स्लॉट चाहिए।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- चिह्नित करें:=0
- स्लॉट:=एक नया नक्शा
- कार्य में प्रत्येक t के लिए, करें
- tf:=स्लॉट[t] अगर t स्लॉट में है
- यदि tf रिक्त नहीं है और tf - टिक> 0 है, तो
- टिक करें:=टिक + tf - टिक करें
- चिह्नित करें:=टिक + 1
- स्लॉट[t] :=टिक + k
- रिटर्न टिक
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
def solve(tasks, k):
tick = 0
slot = {}
for t in tasks:
tf = slot.get(t)
if tf is not None and tf - tick > 0:
tick += tf - tick
tick += 1
slot[t] = tick + k
return tick
tasks = [0, 1, 1, 2]
k = 2
print(solve(tasks, k)) इनपुट
[0, 1, 1, 2]
आउटपुट
6