Show problems as
Classic problem #636MediumArrayStack

Exclusive Time of Functions

Real-world version: Station Machine Minutes
Tracked in this browser only
Read Exclusive Time of Functions on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A workshop runs one machine, shared by stations work stations numbered 0 through stations - 1. A station that holds the machine may hand it to another station for a job of its own and takes it back once that job releases it, so at any minute the stations holding the machine form a stack. A station may even appear more than once in that stack, when a job of its own is nested inside another of its jobs.

log lists what happened, in chronological order. Each entry is a string of three parts joined by |:

  • "3|claim|17" means station 3 took the machine at the very start of minute 17.
  • "3|release|24" means station 3 gave the machine up at the very end of minute 24.

A station that takes the machine at the start of minute 17 and gives it up at the end of minute 24 therefore held it for 8 minutes, minute 17 through minute 24. The machine may also stand idle between one release and the next claim, and idle minutes belong to no station.

The exclusive minutes of a station are the minutes it held the machine itself, leaving out any minute it had handed on to a station further up the stack.

Return an array of length stations whose entry i is the total exclusive minutes of station i over the whole log.

Examples

Example 1

Input
stations = 2, log = ["0|claim|0", "1|claim|2", "1|release|5", "0|release|6"]
Output
[3, 4]

Station 0 held the machine over minutes 0 and 1, handed it to station 1 for minutes 2 through 5, then held it again for minute 6, which is three exclusive minutes against station 1's four.

Example 2

Input
stations = 1, log = ["0|claim|0", "0|claim|2", "0|release|5", "0|release|6"]
Output
[7]

Station 0 is the only station and it held the machine for every minute from 0 to 6, part of the time inside a nested job of its own, so all 7 minutes are its own.

Example 3

Input
stations = 3, log = ["1|claim|0", "1|release|0"]
Output
[0, 1, 0]

Station 1 took the machine at the start of minute 0 and gave it up at the end of the same minute, so it holds one minute; stations 0 and 2 never appear in the log.

Constraints

  • 1 <= stations <= 100
  • 2 <= log.length <= 500
  • Each entry of log reads "<station>|claim|<minute>" or "<station>|release|<minute>"
  • 0 <= station < stations
  • 0 <= minute <= 10^9
  • No two claim entries share a minute
  • No two release entries share a minute
  • Every claim entry is matched by a later release entry for the same station

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def station_minutes(stations: int, log: list[str]) -> list[int]:
Java
public int[] stationMinutes(int stations, List<String> log)

More on the same topics