How do you merge a list of overlapping intervals into the smallest set of non-overlapping intervals?
You sort the intervals by their start times, and then you walk through them and join any that overlap into the one before them.
def merge_intervals(intervals):
ordered = sorted(intervals)
merged = []
for start, end in ordered:
if not merged or start > merged[-1][1]:
merged.append([start, end])
else:
# This one overlaps the last one, so join them.
merged[-1][1] = max(merged[-1][1], end)
return merged
So how does it work? The sort puts the intervals in order of their start, and that is what makes the rest of the algorithm simple. Because they are in order, any interval that overlaps something must overlap the last interval that you have already merged.
Then for each interval you ask one question. Does it start after the last merged interval ends? If it does then it is a new group, so you add it. If it does not then it overlaps the last group, so you extend that group to the later of the two end times.
And the reason for the max is worth knowing about. A later interval can end earlier than the one before it, for example [1, 10] followed by [2, 3]. The merged interval must still end at ten, so you take the bigger of the two ends rather than just overwriting it.
the input [1, 3], [2, 6], [8, 10], [15, 18]
after 1 [1, 3]
after 2 [1, 6] because 2 is inside 1 to 3
after 3 [1, 6], [8, 10]
after 4 [1, 6], [8, 10], [15, 18]
And the complexity is O of n log n for the time, because of the sort, and O of n for the space, because of the answer list. And the walk through the intervals after the sort is O of n.
So the rule to remember is this. Sort by the start, and then only the last merged interval can overlap the next one.
The last question in this topic adds the counting on top.