Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Fixed sort and search solution in Clear category for Painting Wall by nickie
def checkio(num, data):
if num <= 0: return 0
N = len(data)
# sort endpoints in ascending order: O(N*log(N))
events = []
for i, (l, r) in enumerate(data):
events.append((l, True, i))
events.append((r, False, i))
events.sort()
# can we paint num meters with the first i operations? O(N)
def paintable(i):
segments = total = 0
for x, entering, j in events:
if j >= i: continue
if entering:
if segments == 0: start = x
segments += 1
else:
segments -= 1
if segments == 0:
total += x - start + 1
if total >= num: return True
return False
# binary search using paintable: O(N*log(N))
l, r = 0, N
if not paintable(r): return -1
# loop invariant: not paintable(l) and paintable(r)
while r-l > 1:
m = (l+r) // 2
if paintable(m):
r = m
else:
l = m
return r
March 8, 2014
Comments:
