# (c) http://stackoverflow.com/a/16315169
# build ranges first
def expand(list):
newList = []
for r in list:
newList.append(range(r[0], r[1] + 1))
return newList
def compare(list):
toBeDeleted = []
for index1 in range(len(list)):
for index2 in range(len(list)):
if index1 == index2:
# we dont want to compare ourselfs
continue
matches = [x for x in list[index1] if x in list[index2]]
if len(matches) != 0: # do we have overlap?
## compare lengths and get rid of the longer one
if len(list[index1]) > len(list[index2]):
toBeDeleted.append(index1)
break
elif len(list[index1]) < len(list[index2]):
toBeDeleted.append(index2)
# distinct
toBeDeleted = [ toBeDeleted[i] for i,x in enumerate(toBeDeleted) if x not in toBeDeleted[i+1:]]
print len(list)
# remove items
for i in toBeDeleted[::-1]:
del list[i]
return list
import ast, sys
a = ast.literal_eval(sys.stdin.read())
print("Input: %s" % (a,))
print(compare(expand(a)))
IyAoYykgaHR0cDovL3N0YWNrb3ZlcmZsb3cuY29tL2EvMTYzMTUxNjkKIyBidWlsZCByYW5nZXMgZmlyc3QKZGVmIGV4cGFuZChsaXN0KToKICAgIG5ld0xpc3QgPSBbXQogICAgZm9yIHIgaW4gbGlzdDoKICAgICAgICBuZXdMaXN0LmFwcGVuZChyYW5nZShyWzBdLCByWzFdICsgMSkpCiAgICByZXR1cm4gbmV3TGlzdAoKCmRlZiBjb21wYXJlKGxpc3QpOgogICAgdG9CZURlbGV0ZWQgPSBbXQogICAgZm9yIGluZGV4MSBpbiByYW5nZShsZW4obGlzdCkpOgogICAgICAgIGZvciBpbmRleDIgaW4gcmFuZ2UobGVuKGxpc3QpKToKICAgICAgICAgICAgaWYgaW5kZXgxID09IGluZGV4MjoKICAgICAgICAgICAgICAgICMgd2UgZG9udCB3YW50IHRvIGNvbXBhcmUgb3Vyc2VsZnMKICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgIG1hdGNoZXMgPSBbeCBmb3IgeCBpbiBsaXN0W2luZGV4MV0gaWYgeCBpbiBsaXN0W2luZGV4Ml1dCiAgICAgICAgICAgIGlmIGxlbihtYXRjaGVzKSAhPSAwOiAjIGRvIHdlIGhhdmUgb3ZlcmxhcD8KICAgICAgICAgICAgICAgICMjIGNvbXBhcmUgbGVuZ3RocyBhbmQgZ2V0IHJpZCBvZiB0aGUgbG9uZ2VyIG9uZQogICAgICAgICAgICAgICAgaWYgICBsZW4obGlzdFtpbmRleDFdKSA+IGxlbihsaXN0W2luZGV4Ml0pOgogICAgICAgICAgICAgICAgICAgIHRvQmVEZWxldGVkLmFwcGVuZChpbmRleDEpCiAgICAgICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgICAgIGVsaWYgbGVuKGxpc3RbaW5kZXgxXSkgPCBsZW4obGlzdFtpbmRleDJdKToKICAgICAgICAgICAgICAgICAgICB0b0JlRGVsZXRlZC5hcHBlbmQoaW5kZXgyKQogICAgIyBkaXN0aW5jdAogICAgdG9CZURlbGV0ZWQgPSBbIHRvQmVEZWxldGVkW2ldIGZvciBpLHggaW4gZW51bWVyYXRlKHRvQmVEZWxldGVkKSBpZiB4IG5vdCBpbiB0b0JlRGVsZXRlZFtpKzE6XV0gCiAgICBwcmludCBsZW4obGlzdCkKICAgICMgcmVtb3ZlIGl0ZW1zCiAgICBmb3IgaSBpbiB0b0JlRGVsZXRlZFs6Oi0xXToKICAgICAgICBkZWwgbGlzdFtpXSAKICAgIHJldHVybiBsaXN0CgppbXBvcnQgYXN0LCBzeXMKYSA9IGFzdC5saXRlcmFsX2V2YWwoc3lzLnN0ZGluLnJlYWQoKSkKcHJpbnQoIklucHV0OiAlcyIgJSAoYSwpKQpwcmludChjb21wYXJlKGV4cGFuZChhKSkp
W1swLCAxMF0sIFs5LCAxMl0sIFsxMSwgMjBdXQ==
[[0, 10], [9, 12], [11, 20]]