Knowledge Guide
Home › DSA › Dynamic Programming

medium Insert Interval

Problem Statement

Given a list of non-overlapping intervals sorted by their start time, insert a given interval at the correct position and merge all necessary intervals to produce a list that has only mutually exclusive intervals.

Example 1:

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,6]
Output: [[1,3], [4,7], [8,12]]
Explanation: After insertion, since [4,6] overlaps with [5,7], we merged them into one [4,7].

Example 2:

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,10]
Output: [[1,3], [4,12]]
Explanation: After insertion, since [4,10] overlaps with [5,7] & [8,12], we merged them into [4,12].

Example 3:

Input: Intervals=[[2,3],[5,7]], New Interval=[1,4]
Output: [[1,4], [5,7]]
Explanation: After insertion, since [1,4] overlaps with [2,3], we merged them into one [1,4].

Constraints:

Try it yourself

Try solving this question here:

✅ Solution Insert Interval

Problem Statement

Given a list of non-overlapping intervals sorted by their start time, insert a given interval at the correct position and merge all necessary intervals to produce a list that has only mutually exclusive intervals.

Example 1:

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,6]
Output: [[1,3], [4,7], [8,12]]
Explanation: After insertion, since [4,6] overlaps with [5,7], we merged them into one [4,7].

Example 2:

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,10]
Output: [[1,3], [4,12]]
Explanation: After insertion, since [4,10] overlaps with [5,7] & [8,12], we merged them into [4,12].

Example 3:

Input: Intervals=[[2,3],[5,7]], New Interval=[1,4]
Output: [[1,4], [5,7]]
Explanation: After insertion, since [1,4] overlaps with [2,3], we merged them into one [1,4].

Constraints:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 105
  • intervals is sorted by starti in ascending order.
  • newInterval.length == 2
  • 0 <= start <= end <= 105

Solution

If the given list was not sorted, we could have simply appended the new interval to it and used the merge() function from Merge Intervals. But since the given list is sorted, we should try to come up with a solution better than .

When inserting a new interval in a sorted list, we need to first find the correct index where the new interval can be placed. In other words, we need to skip all the intervals which end before the start of the new interval. So we can iterate through the given sorted listed of intervals and skip all the intervals with the following condition:

intervals[i].end < newInterval.start

Once we have found the correct place, we can follow an approach similar to Merge Intervals to insert and/or merge the new interval. Let’s call the new interval ‘a’ and the first interval with the above condition ‘b’. There are five possibilities:

Image
Image

The diagram above clearly shows the merging approach. To handle all four merging scenarios, we need to do something like this:

    c.start = min(a.start, b.start)
    c.end = max(a.end, b.end)

Step-by-Step Algorithm

  • Create an empty list to store the merged intervals.
  • Traverse the given list of intervals:
    • Add all intervals that end before the new interval starts to the merged list.
    • For overlapping intervals:
      • Adjust the start of the new interval to the minimum start time.
      • Adjust the end of the new interval to the maximum end time.
    • Add the merged new interval to the merged list.
    • Add all intervals that start after the new interval ends to the merged list.
  • Return the merged list of intervals.

Algorithm Walkthrough

Using the example Intervals = [[1, 3], [5, 7], [8, 12]], New Interval = [4, 10]:

  • Start with an empty list: mergedIntervals = []
  • First interval [1, 3]:
    • Ends before [4, 10] starts.
    • Add to mergedIntervals: [[1, 3]]
  • Second interval [5, 7]:
    • Overlaps with [4, 10].
    • Adjust new interval: [4, 10] -> [4, 10] (no change)
  • Third interval [8, 12]:
    • Overlaps with [4, 10].
    • Adjust new interval: [4, 10] -> [4, 12]
  • Add merged new interval [4, 12] to mergedIntervals: [[1, 3], [4, 12]]
  • No more intervals left to process.
  • Final merged intervals: [[1, 3], [4, 12]]
Image
Image

Code

Here is what our algorithm will look like:

java
import java.util.*;

/*class Interval {
  int start;
  int end;

  public Interval(int start, int end) {
    this.start = start;
    this.end = end;
  }
};*/

class Solution {

  public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    if (intervals == null || intervals.isEmpty()) return Arrays.asList(
      newInterval
    );

    List<Interval> mergedIntervals = new ArrayList<>();

    int i = 0;
    // skip (and add to output) all intervals that come before the 'newInterval'
    while (
      i < intervals.size() && intervals.get(i).end < newInterval.start
    ) mergedIntervals.add(intervals.get(i++));

    // merge all intervals that overlap with 'newInterval'
    while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
      newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
      newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
      i++;
    }

    // insert the newInterval
    mergedIntervals.add(newInterval);

    // add all the remaining intervals to the output
    while (i < intervals.size()) mergedIntervals.add(intervals.get(i++));

    return mergedIntervals;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    List<Interval> input = new ArrayList<Interval>();
    input.add(new Interval(1, 3));
    input.add(new Interval(5, 7));
    input.add(new Interval(8, 12));
    System.out.print("Intervals after inserting the new interval: ");
    for (Interval interval : sol.insert(
      input,
      new Interval(4, 6)
    )) System.out.print("[" + interval.start + "," + interval.end + "] ");
    System.out.println();

    input = new ArrayList<Interval>();
    input.add(new Interval(1, 3));
    input.add(new Interval(5, 7));
    input.add(new Interval(8, 12));
    System.out.print("Intervals after inserting the new interval: ");
    for (Interval interval : sol.insert(
      input,
      new Interval(4, 10)
    )) System.out.print("[" + interval.start + "," + interval.end + "] ");
    System.out.println();

    input = new ArrayList<Interval>();
    input.add(new Interval(2, 3));
    input.add(new Interval(5, 7));
    System.out.print("Intervals after inserting the new interval: ");
    for (Interval interval : sol.insert(
      input,
      new Interval(1, 4)
    )) System.out.print("[" + interval.start + "," + interval.end + "] ");
    System.out.println();
  }
}

Time Complexity

As we are iterating through all the intervals only once, the time complexity of the above algorithm is , where ‘N’ is the total number of intervals.

Space Complexity

Ignoring the space needed for the result list, the algorithm runs in constant space .

If we include the result list, the space complexity will be as we need to return a list containing all the merged intervals.

🤖 Don't fully get this? Learn it with Claude

Stuck on Insert Interval? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Insert Interval** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Insert Interval** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Insert Interval**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Insert Interval**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Merge IntervalsLongest Substring with At Least K →