सी ++ में कार्यों का विशेष समय

मान लीजिए कि एक सिंगल थ्रेडेड सीपीयू पर हम कुछ फंक्शन निष्पादित करते हैं। अब प्रत्येक फ़ंक्शन में 0 और N-1 के बीच एक अद्वितीय आईडी है। हम लॉग को टाइमस्टैम्प क्रम में संग्रहीत करेंगे जो वर्णन करते हैं कि कोई फ़ंक्शन कब दर्ज किया गया है या बाहर निकला है।

यहां प्रत्येक लॉग एक स्ट्रिंग है जिसे इस प्रारूप में लिखा गया है:"{function_id}:{"start" | "end"}:{timestamp}"। उदाहरण के लिए, यदि स्ट्रिंग "0:प्रारंभ:3" की तरह है, तो इसका मतलब है कि आईडी 0 वाला फ़ंक्शन टाइमस्टैम्प 3 की शुरुआत में शुरू हुआ। "1:अंत:2" का अर्थ है कि आईडी 1 वाला फ़ंक्शन टाइमस्टैम्प के अंत में समाप्त हुआ 2. किसी फ़ंक्शन का अनन्य समय इस फ़ंक्शन में बिताए गए समय की इकाइयों की संख्या है।

तो अगर इनपुट n =2 और लॉग्स =["0:start:0", "1:start:2", "1:end:5", "0:end:6"] की तरह है, तो आउटपुट होगा [3,4] हो। ऐसा इसलिए है क्योंकि फ़ंक्शन 0 समय की शुरुआत में शुरू होता है, फिर यह 2 इकाइयों को निष्पादित करता है और समय के अंत तक पहुंचता है। उसके बाद फ़ंक्शन 1 समय 2 की शुरुआत में शुरू होता है, समय की 4 इकाइयों को निष्पादित करता है और समय 5 पर समाप्त होता है। फ़ंक्शन 0 समय 6 की शुरुआत में फिर से चल रहा है, और समय 6 के अंत में भी समाप्त होता है, इस प्रकार 1 इकाई समय के लिए निष्पादित होता है। तो हम देख सकते हैं कि फंक्शन 0 कुल समय के 2 + 1 =3 यूनिट को निष्पादित करने में खर्च करता है, और फंक्शन 1 कुल समय के 4 यूनिट को निष्पादित करने में खर्च करता है।

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

• आकार n के सरणी रिट को परिभाषित करें, स्टैक सेंट को परिभाषित करें

• जे:=0, पिछला:=0

• मैं के लिए 0 से लेकर लॉग सरणी के आकार तक - 1

  • अस्थायी:=लॉग [i], जे:=0, आईडी:=0, संख्या:=0, प्रकार:=खाली स्ट्रिंग

• जबकि temp[j] एक कोलन नहीं है

  • आईडी:=आईडी * 10 + अस्थायी [जे] संख्या के रूप में

  • j को 1 से बढ़ाएँ

• j को 1 से बढ़ाएँ

• जबकि temp[j] एक कोलन नहीं है

  • टाइप करें:=टाइप कॉन्टेनेट टेम्प [जे]

  • j को 1 से बढ़ाएँ

• j को 1 से बढ़ाएँ

• जबकि j <अस्थायी का आकार

  • संख्या:=संख्या * 10 + अस्थायी [जे] संख्या के रूप में

  • j को 1 से बढ़ाएँ

• यदि टाइप करें =प्रारंभ करें, तो

  • अगर सेंट खाली नहीं है

    • रिट [स्टैक टॉप एलिमेंट] को संख्या से बढ़ाएँ - पिछला

  • d को st में डालें, पिछला :=num

• अन्यथा

  • x :=सेंट के ऊपर, और स्टैक के शीर्ष को हटा दें

  • ret[x] :=ret[x] + (num + 1) - पिछला

  • पिछला:=संख्या + 1

• वापसी रिट

उदाहरण(C++)

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> exclusiveTime(int n, vector<string>& logs) {
      vector <int> ret(n);
      stack <int> st;
      int id, num;
      int j = 0;
      string temp;
      string type;
      int prev = 0;
      for(int i = 0; i < logs.size(); i++){
         temp = logs[i];
         j = 0;
         id = 0;
         num = 0;
         type = "";
         while(temp[j] != ':'){
            id = id * 10 + (temp[j] - '0');
            j++;
         }
         j++;
         while(temp[j] != ':'){
            type += temp[j];
            j++;
         }
         j++;
         while(j < temp.size()){
            num = num * 10 + temp[j] - '0';
            j++;
         }
         if(type == "start"){
            if(!st.empty()){
               ret[st.top()] += num - prev;
            }
            st.push(id);
            prev = num;
         } else {
            int x = st.top();
            st.pop();
            ret[x] += (num + 1) - prev;
            prev = num + 1;
         }
      }
      return ret;
   }
};
main(){
   vector<string> v = {"0:start:0","1:start:2","1:end:5","0:end:6"};
   Solution ob;
   print_vector(ob.exclusiveTime(2, v));
}

इनपुट

2
["0:start:0","1:start:2","1:end:5","0:end:6"]

आउटपुट

[3, 4, ]