Intervals

Updated Nov 19, 2026 · 3 min read
On this page

    Interval questions give you pairs like [start, end]: meetings, bookings, time ranges, IP ranges. Comparing every pair is O(n²). The fix is almost always the same first move: sort by start. After that, any interval can only overlap the ones right before it, and one pass is enough.

    When to recognise it

    • The input is a list of ranges: meetings, bookings, [start, end] pairs, busy times.
    • Merge, insert, remove overlaps, "free time between", "can one person attend all": sort by start, then sweep.
    • "How many at the same time?", minimum rooms, maximum concurrent users: count with a sweep line or a heap of end times.
    • "Keep as many non-overlapping as possible" / remove the fewest: sort by end instead. That one is greedy, see Greedy.

    How it works

    After sorting by start, compare each interval with the last interval in your result. There are only three cases.

    Three pairs of bars. Apart: b starts after a ends, so start a new group. Overlap: b starts inside a, new end is max of the two ends. Inside: b sits inside a, and the end stays a's end.
    Three pairs of bars. Apart: b starts after a ends, so start a new group. Overlap: b starts inside a, new end is max of the two ends. Inside: b sits inside a, and the end stays a's end.

    The third case is the one people miss: the new end is max(last.end, end), not just end.

    Template: merge

    def merge(intervals):
        """Sort by start, then keep extending the last merged interval."""
        out = []
        for s, e in sorted(intervals):
            if out and s <= out[-1][1]:          # overlaps (touching counts)
                out[-1][1] = max(out[-1][1], e)  # max: the new one may sit inside
            else:
                out.append([s, e])
        return out

    Time O(n log n) for the sort, O(n) for the output. Whether touching intervals ([1, 4] and [4, 5]) merge depends on the question; here <= merges them. Ask.

    Template: how many at once

    Turn each interval into two events, +1 at its start and −1 at its end, sort the events, and keep a running total. The maximum running total is the number of rooms you need.

    Meetings [0, 30), [5, 10), [15, 20) on a time line. Events +1 at 0, 5, 15 and −1 at 10, 20, 30. The live count goes 1, 2, 1, 2, 1, 0, so the maximum is 2.
    Meetings [0, 30), [5, 10), [15, 20) on a time line. Events +1 at 0, 5, 15 and −1 at 10, 20, 30. The live count goes 1, 2, 1, 2, 1, 0, so the maximum is 2.
    def max_overlap(intervals):
        """Sweep line: +1 at each start, -1 at each end. Half-open [s, e): ends sort before starts."""
        events = []
        for s, e in intervals:
            events.append((s, 1))
            events.append((e, -1))
        events.sort()                # (t, -1) comes before (t, +1)
        live = best = 0
        for _, d in events:
            live += d
            best = max(best, live)
        return best

    With half-open intervals [s, e), a meeting that ends at 10 does not clash with one that starts at 10. Sorting (time, delta) tuples puts −1 before +1 at the same time, which handles that for free.

    The heap version gives the same number and also tells you which room frees up first, which helps for follow-ups like "assign room ids":

    import heapq
    
    def min_rooms(intervals):
        """Heap of end times: same answer as max_overlap, also tells you which room frees first."""
        ends = []
        for s, e in sorted(intervals):
            if ends and ends[0] <= s:
                heapq.heapreplace(ends, e)    # reuse the room that freed earliest
            else:
                heapq.heappush(ends, e)
        return len(ends)

    Insert into a sorted, non-overlapping list

    Insert Interval needs no sort: copy every interval that ends before the new one starts, merge every interval that overlaps it (take min of starts and max of ends), then copy the rest. Three short loops, O(n).

    Common bugs

    • Forgetting to sort, or sorting by end when you meant start.
    • out[-1][1] = end instead of max(...), which shrinks an interval that contains the new one.
    • Closed vs half-open ends. Decide whether [1, 3] and [3, 5] overlap before writing the comparison, and say it out loud.
    • Mutating the input while iterating over it. Build a new list.
    • Sweep-line ties in the wrong order: processing a start before an end at the same time reports one room too many.

    Say this in the interview

    • "Once the intervals are sorted by start, an interval can only overlap the last merged one, so one pass after an O(n log n) sort is enough."
    • "For the number of rooms, I count how many meetings are live at each moment: +1 at a start, −1 at an end, and the peak is the answer."

    Problems for this pattern

    1. Meeting Rooms: sort and check neighbours.
    2. Merge Intervals: the merge template.
    3. Insert Interval: before, overlapping, after.
    4. Non-overlapping Intervals: sort by end, greedy.
    5. Meeting Rooms II: sweep line or heap.
    6. Interval List Intersections: two pointers over two sorted interval lists.
    7. Employee Free Time: merge everything, then read the gaps.
    8. Design Memory Allocator: free blocks as intervals, merged again on free.

    Related

    Greedy (interval scheduling by earliest end) · Heaps and Top-K (the room heap) · Arrays and Strings