Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Bisect solution in Clear category for Painting Wall by martin_b
import bisect
def checkio(required, operations):
# wall is a simple list, even item is the start, odd item is end of paint
wall, count, paint = [], 1, 0
for f, t in operations:
# find where is the operation
fi = bisect.bisect_left(wall, f)
ti = bisect.bisect_right(wall, t, fi)
# if on odd index, operation is inside existing block,
# use edges of painting from the wall
if fi & 1:
fi, f = fi - 1, wall[fi - 1]
if ti & 1:
ti, t = ti + 1, wall[ti]
# add new painted block
paint += t - f + 1
# remove overlapped blocks
paint -= sum(wall[x + 1] - wall[x] + 1 for x in range(fi, ti, 2))
# consolidate wall
wall = wall[:fi] + [f, t] + wall[ti:]
if paint >= required:
return count
count += 1
return -1
Jan. 25, 2017
