[Stack] Add a solution to Exclusive Time of Functions

soapyigu · soapyigu · commit 0550b87c7453 · 2019-12-31T21:43:41.000-08:00
diff --git a/README.md b/README.md
@@ -4,7 +4,7 @@
 ![Leetcode](./logo.png?style=centerme)
 
 ## Progress
-[Problem Status](#problem-status) shows the latest progress to all 1000+ questions. Currently we have 315 completed solutions. Note: questions with &hearts; mark means that you have to **Subscript to premium membership** of LeetCode to unlock them.
+[Problem Status](#problem-status) shows the latest progress to all 1000+ questions. Currently we have 316 completed solutions. Note: questions with &hearts; mark means that you have to **Subscript to premium membership** of LeetCode to unlock them.
 
 ## Contributors
 
@@ -164,6 +164,7 @@
 [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)| [Swift](./Stack/ValidParentheses.swift)| Easy| O(n)| O(n)|
 [Longest Valid Parentheses](https://leetcode.com/problems/longest-valid-parentheses/)| [Swift](./Stack/LongestValidParentheses.swift)| Hard| O(n)| O(n)|
 [Evaluate Reverse Polish Notation](https://leetcode.com/problems/evaluate-reverse-polish-notation/)| [Swift](./Stack/EvaluateReversePolishNotation.swift)| Medium| O(n)| O(n)|
+[Exclusive Time of Functions](https://leetcode.com/problems/exclusive-time-of-functions/)| [Swift](./Stack/ExclusiveTimeFunctions.swift) | Medium| O(n)| O(n)|
 [Simplify Path](https://leetcode.com/problems/simplify-path/)| [Swift](./Stack/SimplifyPath.swift)| Medium| O(n)| O(n)|
 [Remove K Digits](https://leetcode.com/problems/remove-k-digits/)| [Swift](./Stack/RemoveKDigits.swift)| Medium| O(n)| O(n)|
 [Ternary Expression Parser](https://leetcode.com/problems/ternary-expression-parser/)| [Swift](./Stack/TernaryExpressionParser.swift)| Medium| O(n)| O(n)|
diff --git a/Stack/ExclusiveTimeFunctions.swift b/Stack/ExclusiveTimeFunctions.swift
@@ -0,0 +1,36 @@
+/**
+ * Question Link: https://leetcode.com/problems/exclusive-time-of-functions/
+ * Primary idea: Use a stack to keep task start time, update it when a new task starts.
+ * Time Complexity: O(n), Space Complexity: O(n)
+ */
+
+class ExclusiveTimeFunctions {
+    func exclusiveTime(_ n: Int, _ logs: [String]) -> [Int] {
+        var stack = [(Int, Int)](), res = Array(repeating: 0, count: n)
+        
+        for log in logs {
+            // parse log
+            let logInfo = log.components(separatedBy: ":")
+            let id = Int(logInfo[0])!, isStart = logInfo[1] == "start", time = Int(logInfo[2])!
+            
+            if isStart {
+                if let last = stack.last {
+                    res[last.0] += time - last.1
+                }
+                
+                stack.append((id, time))
+            } else {
+                let startTime = stack.removeLast().1
+                
+                res[id] += time - startTime + 1
+                
+                if var last = stack.last {
+                    last.1 = time + 1
+                    stack[stack.count - 1] = last
+                }
+            }
+        }
+        
+        return res
+    }
+}
