Insert Interval into Sorted List in DSA Java

Mental Model

We add a new time slot into a list of sorted time slots and merge any overlapping ones to keep the list neat and ordered.

Analogy: Imagine you have a schedule with booked meeting times sorted by start time. You want to add a new meeting and adjust the schedule so no meetings overlap, merging any that do.

Intervals list:
[1,3] -> [6,9] -> null
Insert interval:
[2,5]

Dry Run Walkthrough

Input: Intervals: [1,3] -> [6,9], Insert: [2,5]

Goal: Insert [2,5] into the sorted list and merge overlapping intervals to keep the list sorted and non-overlapping.

Step 1: Start with empty result list, iterate intervals to add all intervals ending before new interval starts

[1,3] -> [6,9], Insert: [2,5], Result: []

Why: Add intervals that come completely before the new interval without overlap

Step 2: Check interval [1,3], it overlaps with [2,5], merge to [1,5]

Merged interval: [1,5], Remaining intervals: [6,9], Result: []

Why: Merge overlapping intervals to keep schedule clean

Step 3: Check interval [6,9], no overlap with merged [1,5], add merged interval to result

Result: [1,5], Remaining intervals: [6,9]

Why: Add merged interval before adding intervals that come after

Step 4: Add remaining interval [6,9] to result

Result: [1,5] -> [6,9]

Why: Add intervals that come after the new merged interval

Result:

1 -> 5 -> 6 -> 9 -> null

Annotated Code

DSA Java

import java.util.*;

class Interval {
    int start, end;
    Interval(int s, int e) { start = s; end = e; }
    public String toString() { return "[" + start + "," + end + "]"; }
}

public class InsertInterval {
    public static List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> result = new ArrayList<>();
        int i = 0;
        // Add all intervals ending before newInterval starts
        while (i < intervals.size() && intervals.get(i).end < newInterval.start) {
            result.add(intervals.get(i));
            i++;
        }
        // Merge overlapping intervals
        while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
            newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
            newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
            i++;
        }
        // Add merged interval
        result.add(newInterval);
        // Add remaining intervals
        while (i < intervals.size()) {
            result.add(intervals.get(i));
            i++;
        }
        return result;
    }

    public static void main(String[] args) {
        List<Interval> intervals = new ArrayList<>();
        intervals.add(new Interval(1, 3));
        intervals.add(new Interval(6, 9));
        Interval newInterval = new Interval(2, 5);
        List<Interval> result = insert(intervals, newInterval);
        for (int j = 0; j < result.size() - 1; j++) {
            System.out.print(result.get(j).start + " -> ");
        }
        System.out.print(result.get(result.size() - 1).start + " -> " + result.get(result.size() - 1).end + " -> null\n");
    }
}

while (i < intervals.size() && intervals.get(i).end < newInterval.start) {

Add intervals that end before new interval starts to result

while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {

Merge all intervals overlapping with new interval

newInterval.start = Math.min(newInterval.start, intervals.get(i).start);

Update start of merged interval to earliest start

newInterval.end = Math.max(newInterval.end, intervals.get(i).end);

Update end of merged interval to latest end

result.add(newInterval);

Add merged interval to result

while (i < intervals.size()) {

Add remaining intervals after merged interval

Output

1 -> 5 -> 6 -> 9 -> null

Complexity Analysis

Time: O(n) because we iterate through the list of intervals once

Space: O(n) because we create a new list to store the merged intervals

vs Alternative: Compared to inserting and then sorting or merging repeatedly, this approach merges in one pass, saving time

Edge Cases

Empty intervals list

New interval is simply added as the only interval

DSA Java

while (i < intervals.size() && intervals.get(i).end < newInterval.start) {

New interval does not overlap and is before all intervals

New interval is added at the beginning

DSA Java

while (i < intervals.size() && intervals.get(i).end < newInterval.start) {

New interval does not overlap and is after all intervals

New interval is added at the end

DSA Java

while (i < intervals.size()) {

When to Use This Pattern

When you see a problem asking to insert a time slot into a sorted list of intervals and merge overlaps, use the insert-and-merge pattern to keep intervals sorted and non-overlapping.

Common Mistakes

Mistake: Not merging overlapping intervals and just inserting the new interval
Fix: Merge all intervals overlapping with the new interval before adding to result

Mistake: Adding intervals in wrong order causing unsorted result
Fix: Add intervals before new interval, then merged interval, then intervals after to maintain order

Summary

Inserts a new interval into a sorted list and merges overlapping intervals.

Use when you need to add a time slot into a schedule without overlaps.

Merge all overlapping intervals in one pass to keep the list sorted and clean.

Practice

1. What is the main goal when inserting a new interval into a sorted list of non-overlapping intervals?

easy

A. Merge the new interval with overlapping intervals and keep the list sorted

B. Add the new interval at the end without checking overlaps

C. Remove all intervals that come after the new interval

D. Sort the list again after adding the new interval anywhere

Solution

1. Step 1: Understand the problem context

   The list contains sorted, non-overlapping intervals. When inserting a new interval, we must keep the list sorted and merge any overlapping intervals.

2. Step 2: Identify correct insertion behavior

   Simply adding the new interval without merging or sorting breaks the list's properties. Proper merging keeps intervals non-overlapping and sorted.

3. Final Answer:

   Merge the new interval with overlapping intervals and keep the list sorted -> Option A

4. Quick Check:

   Insert interval = Merge and sort [OK]

Hint: Always merge overlapping intervals to keep list sorted [OK]

Common Mistakes:

• Inserting without merging overlaps
• Appending interval without sorting
• Removing intervals unnecessarily

2. Which of the following Java method signatures correctly represents a function to insert an interval into a sorted list of intervals?

easy

A. public void insertInterval(int intervals[], int newInterval[])

B. public List insertInterval(List intervals, int[] newInterval)

C. public int insertInterval(List<int> intervals, int newInterval)

D. public List<int> insertInterval(int[] intervals, int[] newInterval)

Solution

1. Step 1: Analyze parameter types for intervals

   Intervals are pairs of integers, so List is appropriate to hold multiple intervals. The new interval is an int[] of size 2.

2. Step 2: Check return type and parameters

   The method returns a List after insertion. public List insertInterval(List intervals, int[] newInterval) matches this signature correctly.

3. Final Answer:

   public List insertInterval(List intervals, int[] newInterval) -> Option B

4. Quick Check:

   Correct method signature uses List and int[] [OK]

Hint: Use List for intervals and int[] for new interval [OK]

Common Mistakes:

• Using int[] instead of List for intervals
• Wrong return type like void or int
• Using List<int> instead of List

3. Given the intervals [[1,3],[6,9]] and newInterval = [2,5], what is the resulting list after inserting the new interval?

medium

A. [[1,3],[6,9],[2,5]]

B. [[1,3],[2,5],[6,9]]

C. [[1,5],[6,9]]

D. [[2,5],[6,9]]

Solution

1. Step 1: Identify overlapping intervals

   The new interval [2,5] overlaps with [1,3] because 2 ≤ 3. So they merge into [1,5].

2. Step 2: Merge and keep other intervals

   After merging, the list becomes [[1,5],[6,9]] as [6,9] does not overlap.

3. Final Answer:

   [[1,5],[6,9]] -> Option C

4. Quick Check:

   Merged intervals = [[1,5],[6,9]] [OK]

Hint: Merge intervals if new start ≤ current end [OK]

Common Mistakes:

• Not merging overlapping intervals
• Appending new interval without sorting
• Incorrectly splitting intervals

4. Consider this Java code snippet for inserting an interval:

List insertInterval(List intervals, int[] newInterval) {
  List result = new ArrayList<>();
  for (int[] interval : intervals) {
    if (interval[1] < newInterval[0]) {
      result.add(interval);
    } else if (interval[0] > newInterval[1]) {
      result.add(newInterval);
      newInterval = interval;  // Fix to avoid multiple additions
    } else {
      newInterval[0] = Math.min(newInterval[0], interval[0]);
      newInterval[1] = Math.max(newInterval[1], interval[1]);
    }
  }
  result.add(newInterval);
  return result;
}

What is the bug in this code?

medium

A. It adds newInterval multiple times if intervals after it exist

B. It never adds intervals that come before newInterval

C. It modifies the input intervals list directly

D. It does not merge overlapping intervals correctly

Solution

1. Step 1: Analyze insertion of newInterval in else-if block

   When interval[0] > newInterval[1], it adds newInterval to result, but continues looping, causing newInterval to be added again later.

2. Step 2: Identify repeated addition of newInterval

   Because newInterval is added again after the loop, it can be added multiple times, causing duplicates.

3. Final Answer:

   It adds newInterval multiple times if intervals after it exist -> Option A

4. Quick Check:

   Repeated addition of newInterval causes duplicates [OK]

Hint: Add newInterval once after loop to avoid duplicates [OK]

Common Mistakes:

• Adding newInterval inside loop multiple times
• Not updating newInterval correctly
• Forgetting to add remaining intervals

5. You have intervals [[1,2],[3,5],[6,7],[8,10],[12,16]] and newInterval = [4,8]. After inserting and merging, what is the final list?

hard

A. [[1,2],[3,8],[12,16]]

B. [[1,2],[3,5],[6,8],[8,10],[12,16]]

C. [[1,2],[4,8],[12,16]]

D. [[1,2],[3,10],[12,16]]

Solution

1. Step 1: Identify intervals overlapping with [4,8]

   Intervals [3,5], [6,7], and [8,10] overlap with [4,8] because their ranges intersect.

2. Step 2: Merge overlapping intervals

   Merge [3,5], [6,7], [8,10], and [4,8] into one interval [3,10]. The others remain unchanged.

3. Step 3: Construct final list

   The final list is [[1,2],[3,10],[12,16]].

4. Final Answer:

   [[1,2],[3,10],[12,16]] -> Option D

5. Quick Check:

   Merged intervals = [[1,2],[3,10],[12,16]] [OK]

Hint: Merge all overlapping intervals into one continuous interval [OK]

Common Mistakes:

• Not merging all overlapping intervals
• Leaving duplicates of overlapping intervals
• Incorrectly splitting merged intervals