C++ এ ফাংশনের একচেটিয়া সময়

ধরুন একটি সিঙ্গেল থ্রেডেড সিপিইউতে আমরা কিছু ফাংশন এক্সিকিউট করি। এখন প্রতিটি ফাংশনের 0 এবং N-1 এর মধ্যে একটি অনন্য আইডি রয়েছে। আমরা টাইমস্ট্যাম্প ক্রমানুসারে লগগুলি সংরক্ষণ করব যা বর্ণনা করে যে কখন একটি ফাংশন প্রবেশ করা হয় বা প্রস্থান করা হয়৷

এখানে প্রতিটি লগ এই বিন্যাসে লেখা একটি স্ট্রিং:"{function_id}:{"start" | "end"}:{timestamp}"। উদাহরণস্বরূপ, যদি স্ট্রিংটি "0:start:3" এর মত হয় এর মানে হল যে 0 আইডি সহ ফাংশনটি টাইমস্ট্যাম্প 3 এর শুরুতে শুরু হয়েছে৷ "1:end:2" মানে টাইমস্ট্যাম্পের শেষে 1 এর সাথে ফাংশনটি শেষ হয়েছে 2. একটি ফাংশনের একচেটিয়া সময় হল এই ফাংশনে ব্যয় করা সময়ের এককের সংখ্যা৷

সুতরাং ইনপুট যদি n =2 এবং লগ =["0:start:0","1:start:2","1:end:5","0:end:6"] এর মত হয়, তাহলে আউটপুট হবে হতে [3,4]। এর কারণ হল ফাংশন 0 সময় 0 এর শুরুতে শুরু হয়, তারপর এটি সময়ের 2 ইউনিট নির্বাহ করে এবং সময়ের 1 এর শেষে পৌঁছায়। এর পরে ফাংশন 1 সময় 2 এর শুরুতে শুরু হয়, সময়ের 4 ইউনিট কার্যকর করে এবং 5 এ শেষ হয় ফাংশন 0 আবার চলছে সময় 6 এর শুরুতে, এবং সময় 6 এর শেষেও শেষ হয়, এইভাবে 1 ইউনিট সময়ের জন্য কার্যকর করা হয়। সুতরাং আমরা দেখতে পাচ্ছি যে ফাংশন 0 মোট সময়ের 2 + 1 =3 ইউনিট ব্যয় করে এবং ফাংশন 1 মোট সময় নির্বাহের 4 ইউনিট ব্যয় করে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n আকারের একটি অ্যারে রেট সংজ্ঞায়িত করুন, স্ট্যাক st সংজ্ঞায়িত করুন

• j :=0, আগের :=0

• আমি 0 থেকে লগ অ্যারের আকার - 1

  এর মধ্যে

  • temp :=logs[i], j :=0, id :=0, num :=0, টাইপ :=খালি স্ট্রিং

• যখন temp[j] একটি কোলন নয়

  • id :=id * 10 + temp[j] সংখ্যা হিসাবে

  • 1 দ্বারা j বাড়ান

• 1 দ্বারা j বাড়ান

• যখন temp[j] একটি কোলন নয়

  • টাইপ :=টাইপ কনক্যাটেনেট টেম্প[জে]

  • 1 দ্বারা j বাড়ান

• 1 দ্বারা j বাড়ান

• যখন j <তাপমাত্রার আকার

  • num :=num * 10 + temp[j] সংখ্যা হিসাবে

  • 1 দ্বারা j বাড়ান

• যদি টাইপ =শুরু, তারপর

  • যদি st খালি না হয়

    • ret[স্ট্যাক টপ এলিমেন্ট] num – prev

      দ্বারা বাড়ান

  • d ঢোকান st, prev :=num

• অন্যথায়

  • x :=st এর শীর্ষ, এবং স্ট্যাকের শীর্ষ মুছে দিন

  • ret[x] :=ret[x] + (সংখ্যা + 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, ]