Merge Intervals
Solution:
We know that the array may need to be re-merged if during the merge its length has changed
def merge(intervals): orig_len = len(intervals) intervals.sort() if len(intervals) <= 1: return intervals for i in range(0, len(intervals) - 1): if i < len(intervals) - 1 and intervals[i][1] >= intervals[i+1][0]: merged = [intervals[i][0], intervals[i][1] if intervals[i][1] > intervals[i+1][1] else intervals[i+1][1]] intervals[i] = merged intervals.remove(intervals[i+1]) return intervals if orig_len == len(intervals) else merge(intervals) intervals = [[1,3],[2,6],[8,10],[15,18]] print(merge(intervals)) #[[1,6],[8,10],[15,18]] intervals = [[1,4],[0,2],[3,5]] print(merge(intervals)) #[0,5] intervals = [[1,4],[4,5]] print(merge(intervals)) #[[1,5]]