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