Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Flat ranges solution in Clear category for Painting Wall by bryukh
from bisect import bisect
def count_painted(ranges):
"""
Precondition: ranges has even number of elements
"""
return sum(r - l + 1 for l, r in zip(ranges[::2], ranges[1::2]))
def checkio(required, operations):
painted_ranges = [] # it contains ranges as a flat list
for step, op in enumerate(operations):
left, right = op
left_index = bisect(painted_ranges, left)
right_index = bisect(painted_ranges, right)
if left_index % 2:
if not right_index % 2:
painted_ranges.insert(right_index, right)
else:
painted_ranges.insert(left_index, left)
left_index += 1
if not right_index % 2:
painted_ranges.insert(right_index + 1, right)
right_index += 1
painted_ranges = painted_ranges[:left_index] + painted_ranges[right_index:]
if count_painted(painted_ranges) >= required:
return step + 1
return -1
Feb. 27, 2014
Comments:
