14. Merge Conversation Sessions

Problem

A customer's back-and-forth with Fin generates a series of individual message-exchange intervals. For analytics, it's useful to group these into logical "sessions" — merge any intervals that overlap or fall within a small gap tolerance of each other into a single session interval.

Sort by start, sweep, and merge whenever next.start <= current.end + gap_tolerance. Return the merged intervals sorted by start.

Source: src/14_merge_conversation_sessions.py

def merge_sessions(intervals: list[tuple[float, float]], gap_tolerance: float = 0.0) -> list[tuple[float, float]]: ...

>>> merge_sessions([(0, 5), (6, 10), (15, 20)], gap_tolerance=1.0)
[(0, 10), (15, 20)]
>>> merge_sessions([(0, 10), (2, 4), (3, 8)], gap_tolerance=0.0)
[(0, 10)]

Step-by-Step Approach

1. Handle the empty-input edge case first: an empty list of intervals merges to an empty list.
2. Sort the intervals by start time. This is essential — the classic merge-intervals sweep only works once intervals are in start order, since it only ever compares each interval to the most recently merged one.
3. Seed the result with the first (now-earliest-starting) interval as a mutable [start, end] pair.
4. Sweep through the remaining sorted intervals one at a time. For each, compare its start to the end of the last interval currently in the result, plus the gap tolerance.
5. If start <= last.end + gap_tolerance, the new interval belongs in the same session: merge it in by extending last.end to max(last.end, end) — the max matters because a later-starting interval can still be fully nested inside an earlier, longer one.
6. Otherwise, the gap is too large: close off the current session and start a new one with this interval.
7. After the sweep, convert the mutable [start, end] pairs back to tuples for the return value.

The key insight is that once intervals are sorted by start, you never need to look back further than the single most-recently-merged interval — because any earlier interval already has an end <= the current merged interval's end (by the sort order plus the running max), so a single forward sweep with one running "current session" is sufficient, giving O(n log n) total time dominated by the sort.

Reference solution

def merge_sessions(intervals: list[tuple[float, float]], gap_tolerance: float = 0.0) -> list[tuple[float, float]]:
    # Sort by start then single sweep merging adjacent-or-overlapping intervals: O(n log n) time
    if not intervals:
        return []
    # sort by start, doesn't mutate input
    ordered = sorted(intervals, key=lambda iv: iv[0])
    # mutable [start, end]; ordered[1:] below skips this seed
    merged = [list(ordered[0])]
    for start, end in ordered[1:]:
        # merged[-1]: O(1) access to the open session
        if start <= merged[-1][1] + gap_tolerance:
            # max avoids shrinking a nested interval
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    # back to tuples for the declared return type
    return [tuple(m) for m in merged]

Key Functions & Tricks

• sorted(intervals, key=lambda iv: iv[0]) — sorts by start time without mutating the input.
• list(ordered[0]) — tuple to mutable list, since merged[-1][1] is updated in place.
• ordered[1:] — slices off the first element, already consumed to seed merged.
• merged[-1] — negative indexing for O(1) access to the current open session.
• max(merged[-1][1], end) — prevents a nested, shorter interval from shrinking the session.
• [tuple(m) for m in merged] — converts mutable [start, end] lists back to tuples.

How to Recognize This Pattern