Insert Interval: Adding a Range and Merging Overlaps

Insert Interval

What is an interval?

An interval is just a pair of numbers that marks a *start* and an *end* on a number line. We write it as [start, end]. Think of it like booking a meeting room: [1, 4] means "busy from 1 o'clock to 4 o'clock."

In this problem you are given a list of intervals like:

[[1, 4], [6, 7]]

Two important promises are made about this list:

• Sorted — the intervals are already in order by their start time. The first interval starts earliest.
• Non-overlapping — none of the existing intervals touch or cross each other. They are clean, separate ranges.

The task

You are handed *one new interval* and asked to slot it into the list. After inserting it, some ranges might now bump into each other. Wherever that happens, you must merge them into a single bigger range, and return the cleaned-up list.

What does "overlapping" mean?

Two intervals [s1, e1] and [s2, e2] overlap when:

e1 >= s2

In plain words: the first range ends *at or after* the second range begins. If your meeting ends at 4 and another starts at 3, they clash — so they overlap and should be combined into one.

When two ranges overlap, the merged range is:

• start = the smaller of the two starts
• end = the larger of the two ends

Walking through an example

Input:    intervals = [[1, 4], [6, 7]], interval = [3, 6]
Output:   [[1, 7]]

Let's see why the answer is one big range:

1. We try to insert [3, 6].
2. Compare with [1, 4]: does 4 >= 3? Yes, they overlap. Merge them → start is min(1, 3) = 1, end is max(4, 6) = 6. Now we hold [1, 6].
3. Compare [1, 6] with [6, 7]: does 6 >= 6? Yes, they overlap. Merge → start min(1, 6) = 1, end max(6, 7) = 7. Now we hold [1, 7].
4. Nothing is left, so the final answer is [[1, 7]].

The new interval acted like a bridge that connected both old intervals into a single range.

The function you must fill in

using namespace std;
class Solution {
public:
    vector<vector<int>> insertInterval(
        vector<vector<int>> &intervals,
        vector<int> &interval
    ) {

    }
};

A clean way to think about the solution in three phases:

1. Before — copy every interval that ends *before* the new one starts. These are too early to overlap, so leave them alone.
2. Merge — for every interval that overlaps the new one, keep widening the new interval (shrink the start, grow the end) until the overlapping stops. Then add this combined interval once.
3. After — copy every remaining interval that starts *after* the new one ends. These are too late to overlap, so leave them alone too.

Because the list is already sorted, you can do all of this in a single pass from left to right.