0261MediumArrayStack

Station Machine Minutes

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def station_minutes(stations: int, log: list[str]) -> list[int]:

Java

public int[] stationMinutes(int stations, List<String> log)

The intended approach

Time O(L) for a log of L entries, each parsed and handled once.Space O(stations + d) for the totals and a stack of depth d, and the returned array is one of those totals.

Walk the log once with a stack of the stations currently holding the machine and a marker for the first minute not yet credited. A claim credits the station on top of the stack with the minutes from the marker up to but not including the claiming minute, then pushes the new station and moves the marker to that minute. A release credits the station coming off the stack with the minutes from the marker through the releasing minute inclusive, then moves the marker to the minute after it, which is where the station underneath picks up again.

Pythonentry point: station_minutes

def station_minutes(stations, log):
    minutes = [0] * stations
    holding = []
    since = 0
    for entry in log:
        parts = entry.split("|")
        station = int(parts[0])
        minute = int(parts[2])
        if parts[1] == "claim":
            if holding:
                minutes[holding[-1]] += minute - since
            holding.append(station)
            since = minute
        else:
            minutes[holding.pop()] += minute - since + 1
            since = minute + 1
    return minutes

The obvious version

Pair each claim with its release to get every job as a closed minute range, then charge a job its whole span less the spans of the jobs that sit directly inside it, found by testing containment between every pair of jobs. O(m^3) for m jobs.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_station_minutes(stations, log):
    jobs = []
    open_jobs = []
    for entry in log:
        parts = entry.split("|")
        station = int(parts[0])
        minute = int(parts[2])
        if parts[1] == "claim":
            open_jobs.append((station, minute))
        else:
            who, opened = open_jobs.pop()
            jobs.append((who, opened, minute))
    minutes = [0] * stations
    for i, (station, a, b) in enumerate(jobs):
        span = b - a + 1
        for j, (_, c, d) in enumerate(jobs):
            if i == j or not (a < c and d < b):
                continue
            # only subtract jobs sitting directly inside job i
            wrapped = False
            for k, (_, e, f) in enumerate(jobs):
                if k == i or k == j:
                    continue
                if a < e and f < b and e < c and d < f:
                    wrapped = True
                    break
            if not wrapped:
                span -= d - c + 1
        minutes[station] += span
    return minutes

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in