Resample a Power Meter

A smart meter reports how much power a house is using as (time, watts) readings, sent only when the value changes, so they arrive at irregular times. time is a whole number of seconds and watts is a whole number. The power stays at a reading's value until the next reading, with one limit: a reading is trusted for at most max_hold seconds. If the next reading comes later than that (the meter lost its connection), the power is unknown from time + max_hold until the next reading. Before the first reading the power is unknown, and after the last one it holds for max_hold seconds.

The readings are not in time order. If two readings have the same time, the one that comes later in the list replaces the earlier one.

Write resample(readings, start, end, step, max_hold) that turns this into fixed buckets [start, start + step), [start + step, start + 2 * step) and so on, up to end, and returns a list with one value per bucket. The value is the average power over the part of the bucket where the power is known, worked out as round(total / seconds, 2): seconds is how many seconds of the bucket have a known power, and total is the sum of watts x duration over those parts, a whole number. A bucket with no known second has the value None.

Examples

resample([(0, 100), (30, 200), (150, 50)], 0, 180, 60, 1000)
# returns [150.0, 200.0, 125.0]
resample([(10, 400), (200, 100)], 0, 240, 60, 40)
# returns [400.0, None, None, 100.0]
resample([(7, 20), (0, 10)], 0, 10, 10, 5)
# returns [13.75]

In the first example, the bucket from 0 to 60 has 100 watts for 30 seconds and 200 watts for 30 seconds: (3000 + 6000) / 60 = 150.0. In the second, 400 watts is trusted only until second 50, and nothing is known again until second 200. In the last one, 10 watts holds from 0 to 5, the power is unknown from 5 to 7, and 20 watts covers 7 to 10: (50 + 60) / 8 = 13.75.

Constraints

• 0 <= len(readings) <= 200000, times from 0 to 10,000,000, watts from 0 to 20,000.
• end - start is a multiple of step, with at most 100,000 buckets, and max_hold >= 1.
• Readings before start can still cover the first buckets.