merge/sub intervals list

interval_test.py

# -*- 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()