मान लीजिए एक सिंगल-थ्रेडेड CPU पर, हम कुछ फंक्शन निष्पादित करते हैं। अब प्रत्येक फंक्शन की एक विशिष्ट आईडी 0 और N-1 के बीच होती है। हम टाइमस्टैम्प क्रम में लॉग संग्रहीत करेंगे जो बताते हैं कि कोई फंक्शन कब शुरू या समाप्त हुआ।
यहां प्रत्येक लॉग इस प्रारूप में लिखा एक स्ट्रिंग है: "{function_id}:{"start" | "end"}:{timestamp}"। उदाहरण के लिए, यदि स्ट्रिंग "0:start:3" जैसी है, तो इसका मतलब है कि आईडी 0 वाला फंक्शन टाइमस्टैम्प 3 की शुरुआत में शुरू हुआ। "1:end:2" का मतलब है कि आईडी 1 वाला फंक्शन टाइमस्टैम्प 2 के अंत में समाप्त हुआ। एक फंक्शन का विशेष समय इस फंक्शन में बिताई गई समय इकाइयों की संख्या है।
उदाहरण के लिए, यदि इनपुट n = 2 और logs = ["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 का एक सरणी
retपरिभाषित करें, स्टैकstपरिभाषित करें j := 0,prev := 0iको 0 से लॉग सरणी के आकार - 1 तक लूप करेंtemp := logs[i],j := 0,id := 0,num := 0,type := खाली स्ट्रिंग
- जब तक
temp[j] कोलन नहीं हैid := id * 10 + temp[j] को संख्या के रूप मेंjको 1 से बढ़ाएं
jको 1 से बढ़ाएं- जब तक
temp[j] कोलन नहीं हैtype := type को temp[j] के साथ संयोजित करेंjको 1 से बढ़ाएं
jको 1 से बढ़ाएं- जब तक
num := num * 10 + temp[j] को संख्या के रूप मेंjको 1 से बढ़ाएं
- यदि
type = start, तो- यदि
st खाली नहीं हैret[स्टैक शीर्ष तत्व] को num - prev से बढ़ाएं
d को st में डालें,prev := num
- यदि
- अन्यथा
x := st का शीर्ष, और स्टैक के शीर्ष को हटाएंret[x] := ret[x] + (num + 1) - prevprev := num + 1
retलौटाएं
उदाहरण (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, ]