कुल निष्क्रिय समय खोजने के लिए एल्गोरिदम प्रारंभ/समाप्ति समय

Question

कहें कि आपको प्रारंभ और समाप्ति समय दिया गया है।

इसके अलावा आपको उनकी शुरुआत और अंत समय के अनुसार वर्णित नौकरियों की एक सरणी दी जाती है। ये नौकरियां ओवरलैप हो सकती हैं (यानी, एक साथ कई नौकरियां चल रही हैं)। मुझे यह निर्धारित करने का एक तरीका ढूंढना होगा कि कितना समय निष्क्रिय रहता है और कोई नौकरी नहीं चला रहा है।

बेशक, अगर किसी भी समय केवल एक ही नौकरी चल रही है, तो मैं केवल प्रत्येक नौकरी के चलने वाले समय को घटा सकता हूं, लेकिन ओवरलैप भाग ने मुझे स्टंप कर दिया है।

Answer 1

एक एकल सरणी में सभी प्रारंभ और समाप्ति समय रखो, उन्हें टैगिंग या तो शुरू या समाप्ति के समय। समय के साथ सरणी सॉर्ट करें। अब क्रमबद्ध सूची के माध्यम से पुनरावृति, कितने नौकरियों से चल रहे हैं की गिनती रखने:

• काउंटर incrementing जब एक शुरुआत के समय
• पढ़ने काउंटर decrementing जब किसी समाप्ति समय पढ़ने

जब भी आप शून्य से एक तक बढ़ते हैं, कुल निष्क्रिय समय में (current_time - last_time) जोड़ें। यदि आवश्यक हो तो शुरुआत और अंत भी विशेष मामला याद रखें।

Answer 2

समय को सॉर्ट करें, और उसके बाद क्रम में चलाएं।
यदि कोई समय प्रारंभ समय है, तो चल रहे कार्यों की संख्या में 1 जोड़ें।
यदि यह एक बंद होने का समय है, घटाना 1.
कितना समय है पर नज़र रखें कार्यों की संख्या है जब 0.

Answer 3

यहां थोड़ा अलग दृष्टिकोण है। पहला भाग चित्रकारी उद्देश्य के लिए है।

सभी नौकरियों की पूर्ण समयरेखा का प्रतिनिधित्व करने वाली चींटियों की एक सरणी बनाएं। यह घंटों, मिनटों या जो भी आपको चाहिए, में हो सकता है। मैं घंटों का अनुमान लगाऊंगा। सरणी के आकार को सेट करने के लिए सबसे शुरुआती प्रारंभ समय और नवीनतम अंत समय खोजें। सभी तत्वों को शून्य में प्रारंभ करें।

प्रत्येक नौकरी के माध्यम से लूप, प्रत्येक घंटे नौकरी चलने के लिए समयरेखा में काउंटर को बढ़ा रहा है। तो यदि कोई नौकरी 3 बजे से शाम 5 बजे तक चलती है, तो यह दो घंटे है, इसलिए आप उन घंटों के दौरान नौकरी चल रहे थे यह इंगित करने के लिए 3 घंटे और 4 घंटे का स्लॉट बढ़ाएंगे।

टाइमलाइन के माध्यम से लूप, आप कितने शून्यों का सामना करते हैं इसकी गिनती रखते हुए। वे समय स्लॉट हैं जहां कोई नौकरी नहीं चल रही थी।

अब, यदि आप इसे समझते हैं, तो सरणी से छुटकारा पाने में बहुत आसान है। एक (potintially बड़ा) सरणी बनाने के बजाय, बस पूरे समय रेखा के प्रारंभ और समाप्ति समय का ट्रैक रखें। उस सीमा में प्रत्येक घंटे के लिए अपनी सभी नौकरियों के माध्यम से लूप करें और देखें कि उस समय कितने चल रहे हैं। शून्य जो कोई भी निष्क्रिय समय है।

Answer 4

Sort the jobs based on their end times. 

Jobs<startTime,EndTime>[] = contains the Sorted list. 

Take first Job in the list 
Jobs[0] 

intialize: 
    EndTime = Job[0].EndTime 
    StartTime = Job[0].StartTime 
    idleTime =0; 

For i = 1 till Jobs.size 
{ 
    if (Jobs[i].EndTime >= StartTime) 
    { 
     //Do nothing, its overlapping 
    } 
    else 
    { //Previoys Job time doesnot overlap, so get the idle time. 
     idleTime += (StartTime -Jobs[i].EndTime); 
    } 

    StartTime = Jobs[i].StartTime; 
    EndTime = Jobs[i].EndTime; 
} 

Answer 5

आपके पास व्यस्त समय का हिस्सा है, जब एक या अधिक नौकरियां चल रही हैं। निष्क्रिय समय व्यस्त भाग के बीच समय के योग का योग है। स्यूडोकोड:

idle_time = 0 
sort jobs by start time 
foreach job in jobs 
{ 
    if (job.start > current_chunk.end) 
    { 
    idle_time += job.start - current_chunk.end 
    } 
    if (job.end > current_chunk.end) 
    { 
    current_chunk.end = job.end 
    } 
} 

नोट: सादगी के लिए, मैं बाहर कोड पहले तत्व को संभालने के लिए छोड़ दिया है।