LintCode: Function Runtime

Function Runtime



Similar Problems:


Description
Given a series of descriptions of when the function enters and exits, ask how long each function will run.

The function string length does not exceed 1010, the description number does not exceed 1000010000, and the time does not exceed 1e91e9
All descriptions are in chronological order and the input is guaranteed to be correct. Each function first enters and then exits
Ascending output according to function name dictionary order

Example

Give s=["F1 Enter 10","F2 Enter 18","F2 Exit 19","F1 Exit 20"],return["F1|10","F2|1"].

Explanation:
F1 enters from time 10, exits at time 20, and the running time is 10,
F2 enters from time 18, exits at time 19, and the running time is 1.
Give s=["F1 Enter 10","F1 Exit 18","F1 Enter 19","F1 Exit 20"],return["F1|9"].
Explanation:
F1 enters from time 10, exits at time 18 and enters from time 19, 
exits at time 20, and the total running time is 9.

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/function-runtime
// Basic Ideas: two hashmap
// Complexity: Time O(n*log(n)), Space O(n)
/**
 * @param a: The Descriptions
 * @return: Every functions' runtime
 */
import (
    "fmt"
    "strconv"
    "strings"
    "sort"
    )
func getRuntime (a []string) []string {
    m1, m2 := map[string]int{}, map[string]int{}
    for _, s := range a {
        l := strings.Split(s, " ")
        f, e:= l[0], l[1]
        v, _ := strconv.Atoi(l[2])
        if e == "Enter" {
            m1[f] = v
        } else {
            m2[f] += v - m1[f]
        }
    }

    res, keys := []string{}, []string{}
    for f := range m2 { keys = append(keys, f) }
    sort.Strings(keys)
    for _, f := range keys {
        res = append(res, fmt.Sprintf("%s|%d", f, m2[f]))
    }
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.