🎓 A1Learner
🔍
0 of 47 lessons completed

Merging Intervals

Merging intervals is joining time ranges that overlap into one range each. Ranges that touch or overlap become a single range, and ranges apart stay separate.

Recognition signal

A problem fits this pattern when it gives a list of ranges and asks for the joined result. Overlaps must be combined, and separate ranges must stay separate.

signals = [
    "Input is a list of ranges.",
    "Overlapping ranges must be joined.",
    "Separate ranges stay separate."
]
for line in signals:
    print(line)

Template: sort then join

The template sorts by start, then walks once through the ranges. Each new range either extends the current range or starts a fresh one.

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

print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))

Worked problem: touching ranges

Ranges that touch count as overlapping here, since one ends exactly where the next starts. The joined range runs from the first start to the last end.

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

print(merge([[1, 4], [4, 5]]))

Example

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

print(merge([[1, 2], [3, 5], [4, 7], [8, 9]]))

Key points

  • Interval: a pair holding a start and an end.
  • Overlap: a second range starts at or before the first range ends.
  • Sort by start first, so overlapping ranges sit next to each other.
  • Use the larger of the two ends when two ranges are joined.

Sorting puts the ranges in start order. The ranges 3 to 5 and 4 to 7 overlap, so they join into 3 to 7. The other two ranges touch nothing, so they stay as they are.

Note

sorting first means one pass over the ranges is enough.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

What is the first step when joining overlapping ranges?