Insert Interval into Sorted List in DSA Java - Build from Scratch

Insert Interval into Sorted List

📖 Scenario: You are managing a schedule of booked time slots represented as intervals. Each interval shows a start and end time. The schedule is sorted by start times and intervals do not overlap.Now, you want to add a new time slot to this schedule. You need to insert this new interval into the list and merge any overlapping intervals to keep the schedule clean and sorted.

🎯 Goal: Build a Java program that inserts a new interval into a sorted list of non-overlapping intervals and merges any overlaps. The final list should remain sorted and have no overlapping intervals.

📋 What You'll Learn

Create a list of intervals represented as integer arrays with start and end times.

Add a new interval to the list.

Merge overlapping intervals after insertion.

Print the final list of merged intervals.

💡 Why This Matters

🌍 Real World

Managing meeting schedules, booking systems, or calendar events where time slots must not overlap.

💼 Career

Useful for software developers working on calendar apps, booking platforms, or any system that manages time intervals.

1

Create the initial list of intervals

Create a variable called intervals as a List<int[]> and add these exact intervals: {1, 3}, {6, 9}.

DSA Java

// Create the list of intervals
// Your code here

Hint

Use List<int[]> and new ArrayList<>(). Add intervals with intervals.add(new int[]{start, end}).

2

Create the new interval to insert

Create a variable called newInterval as an int[] with the exact values {2, 5}.

DSA Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List intervals = new ArrayList();
        intervals.add(new int[]{1, 3});
        intervals.add(new int[]{6, 9});
        
        // Create the new interval
        // Your code here
    }
}

Hint

Use int[] newInterval = new int[]{2, 5}; to create the new interval.

3

Insert and merge intervals

Write code to insert newInterval into intervals and merge overlapping intervals. Use a new List<int[]> called merged to store the result. Iterate over intervals with for (int[] interval : intervals). Merge intervals that overlap with newInterval. Add merged intervals to merged.

DSA Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List intervals = new ArrayList();
        intervals.add(new int[]{1, 3});
        intervals.add(new int[]{6, 9});
        
        int[] newInterval = new int[]{2, 5};
        
        // Insert and merge intervals
        // Your code here
    }
}

Hint

Use three cases: interval ends before newInterval starts, interval starts after newInterval ends, or intervals overlap. Update newInterval accordingly and add intervals to merged.

4

Print the merged intervals

Use a for loop with int[] interval to iterate over merged and print each interval in the format [start, end] using System.out.println.

DSA Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List intervals = new ArrayList();
        intervals.add(new int[]{1, 3});
        intervals.add(new int[]{6, 9});
        
        int[] newInterval = new int[]{2, 5};
        
        List merged = new ArrayList();
        for (int[] interval : intervals) {
            if (interval[1]  newInterval[1]) {
                merged.add(newInterval);
                newInterval = interval;
            } else {
                newInterval[0] = Math.min(newInterval[0], interval[0]);
                newInterval[1] = Math.max(newInterval[1], interval[1]);
            }
        }
        merged.add(newInterval);
        
        // Print merged intervals
        // Your code here
    }
}

Hint

Use for (int[] interval : merged) and print intervals with System.out.println("[" + interval[0] + ", " + interval[1] + "]").

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