Introduction to Intervals

EditorialUpdated Oct 25, 2026

Two meetings, one question

Your calendar has a meeting from 1 to 3. Someone asks for 2 to 4: that clashes. What about 3 to 5? It starts the moment the first one ends. Whether that's a clash depends on one detail: is the room still taken at 3?

An interval is a start and an end, [start, end]. Two intervals overlap when each one starts no later than the other ends. Write it with A = [a, b] and B = [c, d]:

def overlaps(a, b):
    return a[0] <= b[1] and b[0] <= a[1]        # each starts no later than the other ends

def meetings_clash(a, b):
    return a[0] < b[1] and b[0] < a[1]          # a meeting is over at its end time, so touching is fine

The only question is the touching case, where one ends exactly where the other starts. If the end is part of the interval (closed, [1, 5] includes 5), touching intervals share that point and overlap. If it isn't (half-open, like a meeting that's over at its end time), they don't. Merge Intervals uses closed intervals; meetings are half-open. The problem statement tells you which, usually in an example.

Run on the five pairs below, overlaps said True, True, True, False, False and meetings_clash said True, True, False, False, False: they disagree only on the touching pair.

Five numbered pairs of intervals on one timeline from 0 to 10, A above B, with the part they share shaded. Partial: A [1, 5] and B [3, 8] overlap. Inside: A [1, 9] and B [3, 5] overlap. Touching: A [1, 5] and B [5, 8] meet at 5; they overlap if the ends are included and are apart if not. Apart: A [1, 3] ends before B [5, 8] starts. Apart: B [1, 4] ends before A [6, 9] starts.

Checking a whole calendar is easier once it's sorted. Sorted by start, each meeting only has to be compared with the one just before it: if a meeting starts before the previous one ends, there's a clash. That's Meeting Rooms:

def can_attend_all(meetings):
    meetings = sorted(meetings)                 # by start
    for k in range(1, len(meetings)):
        if meetings[k][0] < meetings[k - 1][1]: # starts before the one before it ends: a clash
            return False
    return True

It returned True for [[9, 10], [13, 15], [10, 12]], where 10 to 12 starts as 9 to 10 ends, and False for [[9, 11], [10, 12]]. Why the neighbour is enough is the whole trick of this lesson, and the next section shows it.

Merge Intervals: sort, then one pass

Merge Intervals asks you to combine every group of overlapping intervals into one. The first idea most people have: find any two that overlap, merge them, and start looking again.

def merge_brute(intervals):
    intervals = [list(x) for x in intervals]
    changed = True
    while changed:                              # merge any overlapping pair, then start again
        changed = False
        for i in range(len(intervals)):
            for j in range(i + 1, len(intervals)):
                a, b = intervals[i], intervals[j]
                if a[0] <= b[1] and b[0] <= a[1]:
                    intervals[i] = [min(a[0], b[0]), max(a[1], b[1])]
                    intervals.pop(j)
                    changed = True
                    break
            if changed:
                break
    return sorted(intervals)

It's correct, and it's slow. When nothing overlaps, it can only say so after comparing every pair: for 10,000 intervals that's 49,995,000 comparisons. On our judge it took 7.8 seconds in Python, past the 5-second limit. Sorting first and making one pass took 9.0 milliseconds.

Why one pass is enough. Sort by start, and keep the merges in a list. The next interval starts at or after every earlier start, so it starts at or after the last merge's start. Every earlier merge ended before the last one started; that's why they're separate. So the next interval can't reach any of them: only the last merge can still overlap it. One comparison per interval decides everything.

The six intervals sorted by start. [1, 4], [2, 3], [4, 6] and [8, 10] are already merged; [9, 12] is next and [15, 18] comes later. The merges so far are [1, 6], done, and [8, 10], the last one. Guides mark 6, where [1, 6] ends, 8, where the last merge starts, and 9, where the next interval starts: 6 < 8 ≤ 9, so [9, 12] can't reach [1, 6].

There are three outcomes for each interval. It starts after the last merge ends: start a new merge. It starts inside the last merge and ends later: stretch the merge's end. It starts inside and ends inside: nothing changes. That last case is why the code takes the max of the two ends.

Merge Intervals, one comparison each — Sorted intervals, one per row: the indigo one is being decided, green ones are already merged. The shaded band is the last merge; the chips below are the merges so far.

vector<vector<int>> mergeIntervals(vector<vector<int>> intervals) {
    sort(intervals.begin(), intervals.end());           // by start, then end
    vector<vector<int>> merged;
    for (const auto& iv : intervals) {
        if (!merged.empty() && iv[0] <= merged.back()[1])     // starts before the last merge ends: overlap
            merged.back()[1] = max(merged.back()[1], iv[1]);  // keep the later end: it may fit inside
        else
            merged.push_back(iv);
    }
    return merged;
}

def merge_intervals(intervals):
    merged = []
    for start, end in sorted(intervals):        # by start, then end
        if merged and start <= merged[-1][1]:   # starts before the last merge ends: overlap
            merged[-1][1] = max(merged[-1][1], end)   # keep the later end: it may fit inside
        else:
            merged.append([start, end])
    return merged

static int[][] mergeIntervals(int[][] intervals) {
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));   // by start; a subtraction can overflow
    List<int[]> merged = new ArrayList<>();
    for (int[] iv : sorted) {
        int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1);
        if (last != null && iv[0] <= last[1])            // starts before the last merge ends: overlap
            last[1] = Math.max(last[1], iv[1]);          // keep the later end: it may fit inside
        else
            merged.add(new int[]{iv[0], iv[1]});
    }
    return merged.toArray(new int[0][]);
}

function mergeIntervals(intervals) {
    const sorted = [...intervals].sort((a, b) => a[0] - b[0]);   // a comparator: plain sort() compares text
    const merged = [];
    for (const [start, end] of sorted) {
        const last = merged[merged.length - 1];
        if (last && start <= last[1])                // starts before the last merge ends: overlap
            last[1] = Math.max(last[1], end);        // keep the later end: it may fit inside
        else
            merged.push([start, end]);
    }
    return merged;
}

Each prints [[1, 6], [8, 12], [15, 18]], [[1, 5]], [[1, 4]], [[1, 2], [5, 6]], [[1, 12]], [[3, 3]] and [[1, 4]] for [[8, 10], [1, 4], [15, 18], [2, 3], [9, 12], [4, 6]], [[1, 4], [4, 5]], [[1, 4], [2, 3]], [[5, 6], [1, 2]], [[1, 10], [2, 3], [4, 12]], [[3, 3]] and [[1, 2], [3, 4], [2, 3]]. Sorting is O(n log n) and the pass is O(n), so O(n log n) in all, with O(n) for the output.

Now do the deciding yourself. Take the sorted intervals in order and say what the merge does with each one. Flip the switch to see what changes when touching intervals stay apart.

Merge as You Go: say what the merge does with each interval, in sorted order

Insert into a sorted list

Insert Interval hands you a list that's already sorted with no overlaps, and one new interval to add. Sorting again would work, but the list is already in order, so one pass is enough. Walk it in three runs: copy the intervals that end before the new one starts; absorb the ones that start before it ends, growing it with min and max; then add it, and copy the rest.

Insert [4, 9] — The sorted list on top and the new interval below. Green intervals are copied as they are; the amber one is being absorbed, and absorbed ones turn dashed. The chips are the output.

def insert_interval(intervals, new):
    start, end = new
    out, i, n = [], 0, len(intervals)
    while i < n and intervals[i][1] < start:    # ends before the new one starts: copy it
        out.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= end:     # starts before the new one ends: absorb it
        start, end = min(start, intervals[i][0]), max(end, intervals[i][1])
        i += 1
    out.append([start, end])
    out.extend(intervals[i:])                   # the rest start after the new one ends
    return out

It returned [[1, 3], [4, 10], [13, 15]] for [[1, 3], [5, 6], [8, 10], [13, 15]] and [4, 9]. The edges work without special cases: inserting [1, 2] before [[3, 5]], [3, 4] after [[1, 2]], and [2, 3] into an empty list gave [[1, 2], [3, 5]], [[1, 2], [3, 4]] and [[2, 3]].

Every interval is looked at once: O(n). Binary search could find where the new interval goes, but the output still has to be written out, so it stays O(n).

Two sorted lists: intersections

Interval List Intersections gives two sorted lists, each with no overlaps inside it, and asks for every piece of time that's in both. Two intervals share [max of the starts, min of the ends] when that isn't empty.

Keep one index in each list. Compare the two current intervals, record what they share, then move past the one that ends first. Say [1, 4] meets [2, 7]: the second list's next interval starts after [2, 7] ends, after 7, and by then [1, 4] is long over. So [1, 4] can't share anything with it or with anything after it, and it's done.

Two pointers over two lists — The first list on top, the second below, the current interval of each in indigo and the ones already passed faded. The shaded band is what they share; the chips are the intersections found.

def intersections(first, second):
    i = j = 0
    out = []
    while i < len(first) and j < len(second):
        lo = max(first[i][0], second[j][0])
        hi = min(first[i][1], second[j][1])
        if lo <= hi:                            # they share [lo, hi]
            out.append([lo, hi])
        if first[i][1] < second[j][1]:          # the one that ends first can't reach anything later
            i += 1
        else:
            j += 1
    return out

It returned [[2, 4], [6, 7], [9, 9], [11, 12]]. [9, 9] is a single moment: [6, 9] and [9, 12] touch, and these are closed intervals. Each step moves one index, so it's O(m + n) for lists of m and n intervals.

The gaps between: free time and parts

Merging tells you when something is busy, so the gaps between merges are the free time. Employee Free Time asks for the moments when nobody is busy: merge everyone's intervals into one list, then read the gaps.

def free_time(schedules):
    busy = merge_intervals([iv for person in schedules for iv in person])
    return [[busy[k][1], busy[k + 1][0]] for k in range(len(busy) - 1)]   # the gaps between merges

For three people, [[1, 4], [10, 12]], [[2, 5], [13, 14]] and [[7, 8]], it returned [[5, 7], [8, 10], [12, 13]].

This is where touching matters again, from the other side. Two meetings at [1, 4) and [4, 6) don't clash: no moment is in both. But together they keep you busy from 1 to 6, with no free time at 4. Free time needs a gap of positive length, so the merge has to join touching intervals here, which is what <= does.

Intervals hide in other problems too. Partition Labels cuts a string into as many parts as possible so that each letter appears in only one part. Each letter spans an interval, from its first appearance to its last, and the parts are those intervals merged:

def partition_labels(s):
    last = {c: i for i, c in enumerate(s)}      # each letter spans from its first to its last appearance
    sizes, start, end = [], 0, 0
    for i, c in enumerate(s):
        end = max(end, last[c])                 # this part must reach every letter it holds
        if i == end:                            # nothing inside reaches further: cut here
            sizes.append(end - start + 1)
            start = i + 1
    return sizes

For "abacbdee" it returned [5, 1, 2]. 'a' spans 0 to 2 and 'b' spans 1 to 4, with 'c' inside, so they merge into the first part, abacb; then d, then ee.

Sorting intervals in your language

Every one of these algorithms starts with a sort, and each language has its own way to get it wrong:

Language	A plain sort	What to write
C++	compares element by element: by start, then end	nothing extra: `sort(intervals.begin(), intervals.end())`
Python	compares element by element: by start, then end	nothing extra: `sorted(intervals)`
Java	throws `ClassCastException` on an `int[][]`	a comparator: `(a, b) -> Integer.compare(a[0], b[0])`
JavaScript	turns each pair into text and compares that	a comparator: `(a, b) => a[0] - b[0]`

Both comparators have a story, run on the judge:

Java: the usual comparator, (a, b) -> a[0] - b[0], subtracts, and a subtraction can overflow: on [[2000000000, …], [-2000000000, …], [5, 6]] it left the list in that order. Integer.compare(a[0], b[0]) sorted it. Merge Intervals keeps its values small, but a problem like Minimum Number of Arrows to Burst Balloons uses values out to ±2³¹.
JavaScript: with no comparator, [[10, 12], [9, 11], [2, 3]] came back as [[10, 12], [2, 3], [9, 11]], because "10" sorts before "2". Merging that order returned [[10, 12]]; the answer is [[2, 3], [9, 12]].

Sorting also changes the caller's list. The four versions above sort a copy (C++ takes the vector by value), so the input you passed in is left alone.

Spotting it

Clues:

start and end pairs: meetings, bookings, time slots, ranges of pages or numbers;
"merge", "overlap", "conflict", "covered", "free time" in the question;
a range per item hiding in the data, like each letter's first and last position.

And the near-misses:

keep the most intervals with no overlap, or remove the fewest: sort by end instead (Interval Scheduling: Sort by End Time).
how many at once, like the rooms you need: merging loses the count. Sweep over the starts and ends (Counting Overlaps with a Sweep Line).
intervals with a profit, choosing the best set: that's dynamic programming (Maximum Profit in Job Scheduling, in Dynamic Programming).
many range updates on small numbers, like passengers on a route: a difference array (Car Pooling, in Prefix Sum).
intervals arriving one at a time, answered as they come: an ordered map keyed by start.

Common mistakes

Merging without sorting. for start, end in intervals:

Only the last merge is checked, and that's only safe in sorted order. On [[8, 10], [1, 4], [15, 18], [2, 3], [9, 12], [4, 6]] it returned [[8, 10], [15, 18]]; the answer is [[1, 6], [8, 12], [15, 18]].

Setting the end instead of the larger end. merged[-1][1] = end

A contained interval shrinks the merge: [2, 3] cut [1, 4] down to [1, 3], and then [4, 6] no longer overlapped. It returned [[1, 3], [4, 6], [8, 12], [15, 18]].

< where the ends are included. if merged and start < merged[-1][1]:

Merge Intervals counts touching as overlapping, so [[1, 4], [4, 5]] must give [[1, 5]]. It returned [[1, 4], [4, 5]].

Never adding the last merge. Keeping the merge in a variable and appending it only when a new one starts loses the final one: [[1, 6], [8, 12]]. Append it after the loop, or keep the merges in the list as above.

Check yourself

Quiz

1 / 6

Multiple choice

Merge Intervals counts touching intervals as overlapping. What do [[1, 4], [4, 5]] become?

Practice problems

From easier to harder:

Meeting Rooms: sort by start and compare each meeting with the one before it.
Merge Intervals: sort, then one pass with the larger end.
Insert Interval: one pass in three runs, no sort.
Partition Labels: each letter's first-to-last span, merged.
Interval List Intersections: two pointers; the one that ends first moves.
Employee Free Time: merge everyone's busy time, then read the gaps.

Next, Interval Scheduling: Sort by End Time: choosing the most intervals that don't overlap.