Time-step events: sort, then process
Events often arrive out of order, each with a time. The simulation must run in time order, so the first move is to sort:
events = [(5, "b"), (2, "a"), (9, "c")] events.sort() # by time, then by name events.sort(key=lambda e: e[0]) # by time only; ties keep input order
Two things to decide from the statement:
- Tie-break: what happens to events at the same time?
sortis stable, so sorting by time alone keeps the original order for ties. Sorting whole tuples would silently tie-break by the next field instead. - Same-time priority: sometimes the statement says one kind goes first (for example, "leaving happens before arriving"). Put that into the sort key:
key=lambda e: (e[0], 0 if e[1] == "out" else 1).
After sorting, walk the events once, update the state, and record what the question asks for: a running value, a maximum, or the state at the end.
In the visual, watch the list reorder in place.
See it run
events = [(5, "b"), (2, "a"), (9, "c")] events.sort() for time, name in events: print(time, name)
Three events, listed out of order.
Practice time-step events: sort, then process
Exercise 1
A rocket checklist has events [time, name] in any order (time is a whole number, 0 or more). Return the list of names in the order they happen: earlier times first. Events at the same time keep the order they have in the input.
Constraints: 0 ≤ len(events) ≤ 10^5.
Example: solution([[3, "x"], [1, "y"], [3, "z"], [1, "w"]]) returns ["y", "w", "x", "z"].
Exercise 2
A water tank holds at most capacity litres and starts empty. events is a list of [time, change] pairs in any order: a positive change pours water in, a negative one drains it. Process the events in time order (events at the same time in input order). After each event the level is clamped to the range 0 to capacity (extra water is lost; draining an empty tank leaves 0).
Return the list of levels after each event, in processing order.
Constraints: 1 ≤ capacity ≤ 10^9, 0 ≤ len(events) ≤ 10^4, times ≥ 0, |change| ≤ 10^9.
Example: solution(10, [[5, -3], [1, 8], [2, 4]]) returns [8, 10, 7] (time 1: 8, time 2: 12 clamped to 10, time 5: 7).
Exercise 3
A parking garage logs events as [time, kind, plate] in any order. kind is "in" (a car enters) or "out" (it leaves). Process events by time. For events at the same time, all "out" events happen before all "in" events; within the same time and kind, keep input order.
- An
"in"for a plate that is already inside is ignored. - An
"out"for a plate that is not inside is ignored.
Return the largest number of cars inside the garage at any moment (0 if there are no events).
Constraints: 0 ≤ len(events) ≤ 10^5, times ≥ 0, plates are non-empty strings.
Example: solution([[1, "in", "A"], [2, "in", "B"], [2, "out", "A"]]) returns 1. At time 2 the out for A is processed before the in for B, so there is never more than one car inside.
The explanation and tasks are public. Running this lesson requires an account with course access.
Practice
Loading Python…Visualizer Watch your code run line by line
Run your code, then choose Play to follow its execution.