Instantly share code, notes, and snippets.

Embed
What would you like to do?
merge/sub intervals list
# -*- coding:utf-8 -*- #
def merge(lists):
sorted_list = sorted(lists)
result = []
(tmp_start, tmp_end) = sorted_list[0]
for (start, end) in sorted_list:
if tmp_end >= start:
tmp_end = max(tmp_end, end)
else:
result.append([tmp_start, tmp_end])
tmp_start = start
tmp_end = end
result.append([tmp_start, tmp_end])
return result
def sub(base_lists, lists):
result = base_lists
for (start, end) in lists:
result = filter(result, start, end)
return [ (start, end) for (start, end) in result if start < end ]
def filter(source_list, start, end):
result = []
for (s_start, s_end) in source_list:
if start < s_start:
result.append((max(s_start, end), s_end))
elif end > s_end:
result.append((s_start, min(s_end, start)))
else:
result.append((s_start, start))
result.append((end, s_end))
return result
def main():
A = [(20,50)]
B = [(32,38),(10,30),(40,60)]
print "{A + B}", merge(A + B)
print "{A - B}", sub(A, B)
if __name__ == "__main__":
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment