Merge intervals | One Hint Away

Clue: overlapping ranges to combine, such as bookings or time slots. Worked example: LeetCode 56, Merge Intervals (Medium).

The idea

One meeting room, five bookings: when is the room busy? First, sort them by start time. Then walk left to right keeping the last busy block. If the next booking starts at or before that block's end, it's the same stretch: push the end out if needed, with max. If it starts after the block ends, there is a free gap; because everything after starts even later, the block is final, so start a new one.

The walk

Bookings [[13, 17], [9, 11], [18, 19], [14, 15], [10, 12]], sorted by start: [9, 11], [10, 12], [13, 17], [14, 15], [18, 19].

next	last block	overlap?	blocks after
[9, 11]		first	[9, 11]
[10, 12]	[9, 11]	10 ≤ 11, yes	[9, 12]
[13, 17]	[9, 12]	13 > 12, no	[9, 12], [13, 17]
[14, 15]	[13, 17]	14 ≤ 17, yes	[9, 12], [13, 17] (end stays 17)
[18, 19]	[13, 17]	18 > 17, no	[9, 12], [13, 17], [18, 19]

Quick check from the post: [[2, 4], [1, 3], [6, 8]] → [[1, 4], [6, 8]]. Sorted, it is [1, 3], [2, 4], [6, 8]; 2 is before 3, so they join.

Pseudocode

Pseudocode · any language

function merge(intervals):
    sort intervals by start
    merged = empty array
    add intervals[0] to merged
    for i from 1 to length(intervals) - 1:
        [start, end] = intervals[i]
        last = merged[length(merged) - 1]
        if start <= last[1]:          // overlap
            last[1] = max(last[1], end)
        else:
            add [start, end] to merged
    return merged

Each pair is [start, end], so last[1] is the last block's end.

The trap: keep the max. A booking inside the block must not shrink it. Write last[1] = end instead of max(last[1], end) and [14, 15] inside [13, 17] drops the end to 15: hours 15 to 17 vanish and you get [13, 15].

Code

import java.util.*;

public class Main {
    static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> merged = new ArrayList<>();
        merged.add(new int[]{intervals[0][0], intervals[0][1]});
        for (int i = 1; i < intervals.length; i++) {
            int start = intervals[i][0], end = intervals[i][1];
            int[] last = merged.get(merged.size() - 1);
            if (start <= last[1]) {             // overlap
                last[1] = Math.max(last[1], end);
            } else {
                merged.add(new int[]{start, end});
            }
        }
        return merged.toArray(new int[0][]);
    }
}

def merge(intervals):
    intervals.sort(key=lambda pair: pair[0])
    merged = []
    merged.append([intervals[0][0], intervals[0][1]])
    for i in range(1, len(intervals)):
        start, end = intervals[i]
        last = merged[-1]
        if start <= last[1]:                # overlap
            last[1] = max(last[1], end)
        else:
            merged.append([start, end])
    return merged

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
    vector<vector<int>> merged;
    merged.push_back({intervals[0][0], intervals[0][1]});
    for (size_t i = 1; i < intervals.size(); i++) {
        int start = intervals[i][0], end = intervals[i][1];
        vector<int>& last = merged.back();
        if (start <= last[1]) {                 // overlap
            last[1] = max(last[1], end);
        } else {
            merged.push_back({start, end});
        }
    }
    return merged;
}

function merge(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    const merged = [];
    merged.push([intervals[0][0], intervals[0][1]]);
    for (let i = 1; i < intervals.length; i++) {
        const [start, end] = intervals[i];
        const last = merged[merged.length - 1];
        if (start <= last[1]) {                 // overlap
            last[1] = Math.max(last[1], end);
        } else {
            merged.push([start, end]);
        }
    }
    return merged;
}

Complexity

Time: O(n log n) for the sort; the sweep after it is one pass, O(n).
Extra space: O(n) for the merged list (plus whatever the language's sort uses).

How it was tested

All four programs were compiled and run on 3,014 cases (the slide examples, edge cases such as one interval, identical intervals, touching intervals like [1, 4] and [4, 5], nested intervals, sorted and reversed input, values up to 10,000, plus 3,000 random cases) and every output matched an independent brute force that repeatedly joins any two overlapping intervals until none overlap. Re-run on 31 October 2026 on 3,004 more cases (3,000 random lists of 1 to 8 intervals with values up to 25, plus the example, the quick check, [[1, 4], [4, 5]] and [[1, 1]]): all four matched on every one.