Introduction

Efficiently merging integer ranges in a stream depends on one crucial detail: whether the incoming ranges are already ordered by start value. If they are sorted, you can merge online with constant extra state. If they are not sorted, exact merging generally requires buffering or another ordering structure.

Define the merge rule first

Most interval-merging tasks combine ranges when they overlap, and some also combine ranges that touch.

Examples:

• overlap merge: [1, 3] and [2, 5] become [1, 5]
• touching merge: [1, 3] and [4, 6] become [1, 6] if adjacency counts as mergeable

Decide that rule before coding. Otherwise, a correct implementation for one use case becomes wrong for another.

Best case: sorted stream

If the stream arrives sorted by range start, you only need to keep the current merged interval and compare each new interval against it.

1from typing import Iterable, Iterator, Tuple
2
3Range = Tuple[int, int]
4
5def merge_sorted_ranges(ranges: Iterable[Range]) -> Iterator[Range]:
6    current = None
7
8    for start, end in ranges:
9        if current is None:
10            current = [start, end]
11            continue
12
13        if start <= current[1] + 1:
14            current[1] = max(current[1], end)
15        else:
16            yield tuple(current)
17            current = [start, end]
18
19    if current is not None:
20        yield tuple(current)
21
22
23data = [(1, 3), (2, 4), (7, 9), (9, 12)]
24print(list(merge_sorted_ranges(data)))

This is the ideal streaming solution because it needs only one active interval plus the current input.

Why unsorted streams are harder

If a later range can begin earlier than a previously seen range, exact online merging becomes harder. For example, after seeing [10, 12], a later [1, 20] changes everything.

That means an unsorted stream generally needs one of these:

• buffer then sort
• maintain an ordered structure such as a tree map
• accept approximate or windowed results

There is no simple one-pass constant-memory exact solution for arbitrary unsorted interval streams.

Batch-then-sort strategy

If you can afford buffering, sorting is still the standard exact approach.

1from typing import List, Tuple
2
3Range = Tuple[int, int]
4
5def merge_ranges(ranges: List[Range]) -> List[Range]:
6    if not ranges:
7        return []
8
9    ranges = sorted(ranges, key=lambda r: r[0])
10    merged = [list(ranges[0])]
11
12    for start, end in ranges[1:]:
13        last = merged[-1]
14        if start <= last[1] + 1:
15            last[1] = max(last[1], end)
16        else:
17            merged.append([start, end])
18
19    return [tuple(r) for r in merged]
20
21
22print(merge_ranges([(5, 7), (1, 3), (2, 4), (10, 10)]))

This is often the right answer unless the stream is truly unbounded.

Event-time windows for long streams

In stream-processing systems, a common compromise is to merge only within a bounded window. For example, you might collect intervals for one minute, sort and merge them, then emit the result. That gives deterministic results with bounded memory, at the cost of not performing a global merge across all time.

This is usually the practical answer in systems such as telemetry or log processing where exact infinite-history merging is not realistic anyway.

Implementation notes in C++

The same sorted-stream logic is easy to express in C++:

1#include <iostream>
2#include <vector>
3
4struct Range {
5    int start;
6    int end;
7};
8
9std::vector<Range> merge_sorted(const std::vector<Range>& ranges) {
10    std::vector<Range> out;
11
12    for (const auto& r : ranges) {
13        if (out.empty() || r.start > out.back().end + 1) {
14            out.push_back(r);
15        } else {
16            out.back().end = std::max(out.back().end, r.end);
17        }
18    }
19
20    return out;
21}

This assumes the input is already sorted. If that assumption is false, sort first or document the contract strictly.

Common Pitfalls

The most common mistake is assuming an unsorted stream can be merged exactly with only one active range in memory. Another is forgetting to define whether touching ranges should merge, which changes results around boundaries such as [3, 5] and [6, 8]. Developers also often sort by the wrong key or skip sorting entirely in the batch case. Off-by-one mistakes are common when integer adjacency is supposed to count as overlap. Finally, some implementations emit partial results too early in a real stream and later discover that a delayed range should have merged with something already sent downstream.

Summary

• If ranges arrive sorted by start, you can merge them online with constant extra state.
• If the stream is unsorted, exact merging usually requires buffering or an ordered data structure.
• Decide whether adjacent integer ranges should merge before implementing the algorithm.
• Sorting plus a linear scan remains the standard exact solution for batched input.
• Windowed merging is often the practical compromise for real unbounded streams.
• Make the ordering assumption explicit in the API or code comments so callers do not misuse the function.