Merging Overlapping Intervals

Sort the intervals by their start time, then walk the sorted list keeping the current merged interval. For each new interval, if it starts at or before the end of the current merged interval, the two overlap, so extend the merged end to the larger of the two ends. Otherwise the current interval is finished and you start a new one.

def merge_intervals(intervals):
    ordered = sorted(intervals)
    merged = []
    for start, end in ordered:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged


data = [(1, 3), (2, 6), (8, 10), (15, 18)]
print(merge_intervals(data))

The output is 1 to 6, 8 to 10 and 15 to 18. The first two intervals overlap, so they merge into one that covers from one to six, because the second one starts before the first one ends and finishes later.

The mechanism is that sorting by start time means every interval that could overlap the current group arrives consecutively. The comparison with the end of the current merged interval, rather than with the end of the previous original interval, is what handles containment. An interval nested entirely inside another one starts before the current end and ends before it, and taking the maximum of the two ends keeps the longer span instead of shrinking it.

The trade-off to name is that the sort costs O of n log n and the scan is linear, so the whole thing is dominated by the sort. The comparison is less than or equal to rather than strictly less, which means intervals that merely touch at a single point are merged. Whether that is right depends on the domain: for a room booking where a meeting ending at eleven frees the room at eleven, touching intervals should stay separate, so the comparison should be strict.

Keep a parallel list of counts. Every time an interval joins the current group, increment its count. When a new group starts, push a fresh count of one alongside the new merged interval.

def merge_intervals_counts(intervals):
    ordered = sorted(intervals)
    merged = []
    counts = []
    for start, end in ordered:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
            counts[-1] += 1
        else:
            merged.append([start, end])
            counts.append(1)
    return merged, counts


data = [(1, 3), (2, 6), (8, 10), (15, 18)]
print(merge_intervals_counts(data))

The outputs are the list 1 to 6, 8 to 10, 15 to 18 and the list 2, 1, 1. The first merged group swallowed two original intervals, and the other two groups each contain one.

The mechanism is that the count belongs to the group, not to the interval. Because the groups are created and extended in lockstep, keeping the two lists in step is straightforward, and the counts list always has the same length as the merged list. The alternative is to store the count inside each merged entry as a third element, which avoids the parallel list but makes the output shape less conventional for callers that expect a list of pairs.

The trade-off to name is that the parallel list has to be kept consistent, and that is exactly the kind of bookkeeping that goes wrong when the code is edited later. If you find yourself maintaining two lists in step, a small helper that appends a group and a helper that extends one are worth the extra lines. There is also a neat alternative: count the groups by comparing each merged interval with the original list after the merge, which costs an extra linear pass but keeps the merge function itself untouched and therefore simpler to trust.