Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Painting Wall by Sim0000
def add(s, x):
if len(s) == 0: return [x[:]]
if s[-1][1] < x[0]: return s + [x]
if x[1] < s[0][0]: return [x] + s
# -[- y[0] <= x[0] <= y[1]
# [ --- x[0] < y[0]
for p0 in range(len(s)):
if x[0] <= s[p0][1]: break
# -]- y[0] <= x[1] <= y[1] : p1
# ] --- x[1] < y[0] : p1 - 1
# ] not found : len(s) - 1
for p1 in range(p0, len(s)):
if x[1] <= s[p1][1]:
if x[1] < s[p1][0]: p1 -= 1
break
return s[:p0] + [[min(x[0], s[p0][0]), max(x[1], s[p1][1])]] + s[p1+1:]
def checkio(num, data):
s = []
for i in range(len(data)):
x = data[i]
s = add(s, x)
total = sum(x[1] - x[0] + 1 for x in s)
if total >= num: return i + 1
return -1
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert checkio(5, [[1, 5], [11, 15], [2, 14], [21, 25]]) == 1, "1st"
assert checkio(6, [[1, 5], [11, 15], [2, 14], [21, 25]]) == 2, "2nd"
assert checkio(11, [[1, 5], [11, 15], [2, 14], [21, 25]]) == 3, "3rd"
assert checkio(16, [[1, 5], [11, 15], [2, 14], [21, 25]]) == 4, "4th"
assert checkio(21, [[1, 5], [11, 15], [2, 14], [21, 25]]) == -1, "not enough"
assert checkio(1000000011, [[1, 1000000000], [11, 1000000010]]) == -1, "large"
March 1, 2014
Comments:
