पायथन में समान प्रकार के कार्यों के बीच k समय अंतराल के साथ कार्यों को पूरा करने के लिए न्यूनतम समय खोजने का प्रोग्रम

मान लीजिए हमारे पास tasks नामक पूर्णांकों की एक सूची है जहां प्रत्येक आइटम एक अलग कार्य प्रकार का प्रतिनिधित्व करता है, हमारे पास एक गैर-ऋणात्मक पूर्णांक k भी है। प्रत्येक कार्य को पूरा करने में एक इकाई समय लगता है और कार्यों को सही क्रम में पूरा किया जाना चाहिए, लेकिन हमें दो समान प्रकार के कार्यों को करने के बीच k इकाई समय होना चाहिए। किसी भी समय, या तो हम एक कार्य कर सकते हैं या प्रतीक्षा कर सकते हैं। हमें सभी कार्यों को पूरा करने में लगने वाला समय ढूंढना है।

इसलिए, यदि इनपुट है tasks = [0, 1, 1, 2], k = 2, तो आउटपुट होगा 6, क्योंकि पहले दो कार्य अलग प्रकार के हैं, इसलिए उन्हें बिना किसी अंतराल के निष्पादित किया जा सकता है, अब समय 2 पर, अगला कार्य समान प्रकार का कार्य है इसलिए हमें 2-समय स्लॉट के लिए प्रतीक्षा करनी होगी, फिर कार्य करें और अंत में अन्य प्रकार का कार्य, प्रकार 2 है। तो यह कार्य करें। तो यह [0, 1, wait, wait, 1, 2] जैसा है। इससे हम पहचान सकते हैं, हमें 6 समय स्लॉट चाहिए।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

tick := 0
slot := एक नया मैप
tasks में प्रत्येक t के लिए, करें:
- tf := slot[t] यदि t slot में है
- यदि tf शून्य नहीं है और tf - tick > 0, तो:
  - tick := tick + tf - tick
- tick := tick + 1
- slot[t] := tick + k
tick लौटाएं

उदाहरण

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

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], 2