Insert Interval

MEDIUM✓ CHIP-TIMEDLC #57 — FULL STATEMENT ↗

The drill: A calendar already holds non-overlapping meetings sorted by start time. Drop one more meeting in, merging it with anything it touches, and hand back the calendar in order.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A calendar of meetings arrives already sorted by start time, with no two meetings overlapping each other. One additional meeting needs to be dropped into that calendar.

Wherever the new meeting overlaps or touches an existing one, those meetings merge into a single wider block covering their combined span — this can chain across several existing meetings at once if the new one bridges them.

The result is the full calendar again, still sorted by start time and still with no two entries overlapping, reflecting the new meeting's insertion and any merges it caused.

EX 01

intervals = [[1, 4], [8, 10]] · newInterval = [5, 7]

→ [[1, 4], [5, 7], [8, 10]]

NEW INTERVAL FITS IN THE GAP, NO MERGE

EX 02

intervals = [[2, 4], [6, 8], [10, 12]] · newInterval = [5, 7]

→ [[2, 4], [5, 8], [10, 12]]

OVERLAPS ONLY THE MIDDLE INTERVAL

EX 03

intervals = [] · newInterval = [3, 5]

→ [[3, 5]]

EMPTY CALENDAR

existing meetings arrive already sorted by start time, non-overlapping
the new meeting can overlap, touch, or sit apart from any of them
touching intervals (end equals next start) count as overlapping and merge
the returned calendar stays sorted and fully non-overlapping

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The intervals well before the new one's reach and the ones well after it never change — only the ones the new interval overlaps need any work. What three groups is the array splitting into?

HINT 2 THE STRUCTURE

Walk left to right: intervals ending strictly before the new one starts pass through untouched, intervals starting strictly after the new one ends pass through untouched, and everything else — the new interval included — belongs to one merge.

HINT 3 ONE STEP FROM THE ANSWER

Copy the untouched-left intervals as-is, absorb every overlapping interval into the new one by widening its start and end, then append the untouched-right intervals.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE ONE-PASS SPLICEPATTERN · GREEDY — LINEAR SWEEPintervals = [[2,4],[6,8],[10,12]] · newInterval = [5, 7]

[2,4]

[6,8]

[10,12]

RESULT / MERGING WINDOW

result → []

new → [5, 7]

STEP 1

Drop [5, 7] into the sorted calendar [[2,4],[6,8],[10,12]]. Untouched-left, then absorb overlaps, then untouched-right.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/insert-interval.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []
        i, n = 0, len(intervals)
        start, end = newInterval

        while i < n and intervals[i][1] < start:
            result.append(intervals[i])
            i += 1

        while i < n and intervals[i][0] <= end:
            start = min(start, intervals[i][0])
            end = max(end, intervals[i][1])
            i += 1
        result.append([start, end])

        while i < n:
            result.append(intervals[i])
            i += 1

        return result

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 21 LN

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        combined = intervals + [newInterval]
        combined.sort(key=lambda iv: iv[0])
        merged = []
        for start, end in combined:
            if merged and start <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], end)
            else:
                merged.append([start, end])
        return merged

TIME O(N LOG N)SPACE O(N)PYTHON · TRAINING PACE · 11 LN

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0, n = intervals.length;
        int start = newInterval[0], end = newInterval[1];

        while (i < n && intervals[i][1] < start) {
            result.add(intervals[i]);
            i++;
        }

        while (i < n && intervals[i][0] <= end) {
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        result.add(new int[] { start, end });

        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

        return result.toArray(new int[0][]);
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 26 LN

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> combined = new ArrayList<>();
        for (int[] iv : intervals) combined.add(iv);
        combined.add(newInterval);
        combined.sort((a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> merged = new ArrayList<>();
        for (int[] iv : combined) {
            if (!merged.isEmpty() && iv[0] <= merged.get(merged.size() - 1)[1]) {
                int[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], iv[1]);
            } else {
                merged.add(new int[] { iv[0], iv[1] });
            }
        }
        return merged.toArray(new int[0][]);
    }
}

TIME O(N LOG N)SPACE O(N)JAVA · TRAINING PACE · 19 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED