Card 07/ 08
Practice: Counting Coats of Paint Along a Road
Crews paint stretches of road from kilometre a to b inclusive: how many coats does each kilometre get, in one pass after the crews are read?
A prefix sum also runs in reverse: marking where each range starts and ends, then taking the running total of the marks, gives how many ranges cover each position. Three crews paint lines on a road of kilometres 0 to 8: one from kilometre 1 to 4, one from 3 to 7 and one from 4 to 5, each inclusive. Find how many coats each kilometre gets, reading the crews once and then making one pass along the road. Then say where the second mark of each crew goes, and why.
Show the coats and a solution
The coats along kilometres 0 to 8 are 0 1 1 2 3 2 1 1 0. A difference array, an array of changes whose running total is the answer, holds +1 at each crew's first kilometre and −1 at the kilometre after its last, b + 1, because the last kilometre is still painted. Marking −1 at b would stop each coat one kilometre early.
| Kilometre | Mark | Coats |
|---|---|---|
| 0 | 0 | 0 |
| 1 | +1 | 1 |
| 2 | 0 | 1 |
| 3 | +1 | 2 |
| 4 | +1 | 3 |
| 5 | −1 | 2 |
| 6 | −1 | 1 |
| 7 | 0 | 1 |
| 8 | −1 | 0 |
The listing makes the marks, then takes their running total.
def coats_per_kilometre(crews: list[tuple[int, int]], kilometres: int) -> tuple[list[int], list[int]]:
marks = [0] * (kilometres + 1)
for first, last in crews:
marks[first] += 1
marks[last + 1] -= 1
coats, running = [], 0
for kilometre in range(kilometres):
running += marks[kilometre]
coats.append(running)
return marks[:kilometres], coats
crews = [(1, 4), (3, 7), (4, 5)]
marks, coats = coats_per_kilometre(crews, 9)
print("marks", *marks)
print("coats", *coats)marks 0 1 0 1 1 -1 -1 0 -1
coats 0 1 1 2 3 2 1 1 0The marks array has one spare slot, for a crew that ends on the last kilometre. Reading c crews is O(c), and the pass is O(n) for n kilometres, against O(c × n) for painting each crew's kilometres one by one.
← → move through sections and cards