Intervals

When to reach for it

• Merging overlapping ranges into the fewest blocks.
• Inserting a new range into a sorted list of ranges.
• Finding the overlap between two people's calendars, or the gaps where everyone is free.
• Counting how many ranges are active at once: rooms needed, peak concurrency.

The core idea

Once intervals are sorted by start, an interval can only overlap the one you kept last, not anything earlier, so one pass decides everything. Two intervals [a, b] and [c, d] with a <= c overlap exactly when c <= b (or c < b if touching ends do not count). Merging extends the last kept interval's end to max(b, d).

When the question is about how many intervals are open at the same moment, sweep instead: turn each interval into a start event and an end event, sort the events by time, and keep a running count. Decide up front which comes first when a start and an end share a time.

A Python template

def insert_range(ranges, new):
    """ranges are sorted and non-overlapping; returns them with new merged in."""
    out, i, n = [], 0, len(ranges)
    while i < n and ranges[i][1] < new[0]:      # wholly before new
        out.append(ranges[i]); i += 1
    start, end = new
    while i < n and ranges[i][0] <= end:         # overlapping: absorb
        start, end = min(start, ranges[i][0]), max(end, ranges[i][1])
        i += 1
    out.append([start, end])
    out.extend(ranges[i:])                       # wholly after new
    return out

def overlaps(a, b):
    """Both lists sorted and non-overlapping; returns their intersections."""
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        lo, hi = max(a[i][0], b[j][0]), min(a[i][1], b[j][1])
        if lo <= hi:
            out.append([lo, hi])
        if a[i][1] < b[j][1]:                    # drop whichever ends first
            i += 1
        else:
            j += 1
    return out

Time and space

Sorting dominates at O(n log n); the pass afterwards is O(n). If the input is already sorted, as in both template functions, the work is linear: O(n) for an insert, O(m + n) for intersecting two lists. Output space is O(n).

Common mistakes

• Forgetting to sort first, or sorting by end when the merge assumes sorted starts.
• Not deciding whether touching intervals, like 10:00 to 11:00 and 11:00 to 12:00, count as overlapping.
• Setting the merged end to the later interval's end instead of the maximum of both ends.
• Mixing time zones or units when the intervals come from different people.
• Mutating the input list in place when the caller still needs it, without saying so.

How to explain it out loud

Ask about the boundaries before you code: "Do meetings that touch at 11:00 conflict?" It is a real clarifying question with a real effect on the code, and interviewers notice when you ask it. Then say why sorting makes one pass enough: once sorted, an interval can only overlap the last one kept.

Trace an example with a contained interval (one wholly inside another), which is where merges most often go wrong, and give O(n log n). Naming the containment and touching cases before the interviewer does is what Devana counts toward edge cases.