Insert Interval into Sorted List in DSA Java - Deep Dive

Overview - Insert Interval into Sorted List

What is it?

Insert Interval into Sorted List means adding a new time range into a list of existing time ranges that are sorted and do not overlap. The goal is to keep the list sorted and merge any overlapping intervals after insertion. This helps manage schedules, bookings, or any continuous ranges efficiently.

Why it matters

Without this concept, managing overlapping time ranges would be complicated and error-prone. For example, scheduling systems would fail to merge overlapping appointments, causing confusion and conflicts. This method ensures that the list remains clean, sorted, and easy to query or update.

Where it fits

Before learning this, you should understand arrays or lists and how sorting works. After this, you can learn about interval trees or advanced range queries for more complex interval management.

Mental Model

Core Idea

Insert the new interval in order, then merge all overlapping intervals to keep the list sorted and non-overlapping.

Think of it like...

Imagine you have a row of books sorted by their thickness. You want to add a new book in the right place and then combine any books that are glued together to form a bigger book.

Sorted intervals list:
┌───────────┐
│ [1,3]     │
│     [6,9] │
└───────────┘
Insert new interval [2,5]:
Step 1: Place it in order:
┌─────────────────────┐
│ [1,3], [2,5], [6,9] │
└─────────────────────┘
Step 2: Merge overlaps:
[1,3] and [2,5] overlap -> merge to [1,5]
Final list:
┌───────────┐
│ [1,5]     │
│     [6,9] │
└───────────┘

Build-Up - 6 Steps

1

Foundation

Understanding Intervals and Sorting

Concept: Intervals are pairs of numbers representing ranges, and sorting means arranging them by their start times.

An interval is like a time slot with a start and end. For example, [1,3] means from time 1 to 3. A sorted list of intervals means each interval starts after the previous one ends or at least starts later. Example: [1,3], [6,9] is sorted because 6 > 3.

Result

You can quickly find where a new interval fits by comparing start times.

Understanding intervals and sorting is essential because insertion depends on placing the new interval in the correct order.

2

Foundation

Detecting Overlapping Intervals

Concept: Two intervals overlap if one starts before the other ends.

Given intervals [a,b] and [c,d], they overlap if c ≤ b and a ≤ d. For example, [1,3] and [2,5] overlap because 2 ≤ 3 and 1 ≤ 5. If they overlap, they can be merged into [min(a,c), max(b,d)].

Result

You can identify which intervals need merging after insertion.

Knowing how to detect overlaps allows you to merge intervals correctly and keep the list clean.

3

Intermediate

Inserting Interval in Sorted List

Concept: Insert the new interval in the correct position based on start time without merging yet.

Traverse the list from the start. Find the first interval whose start is greater than the new interval's start. Insert the new interval before it. If none found, append at the end. Example: Insert [2,5] into [1,3], [6,9] -> [1,3], [2,5], [6,9].

Result

The list remains sorted by start times but may have overlaps.

Inserting in order simplifies the next step of merging by ensuring intervals are in sequence.

4

Intermediate

Merging Overlapping Intervals After Insertion

🤔Before reading on: do you think merging should be done before or after inserting the new interval? Commit to your answer.

Concept: After insertion, merge all intervals that overlap with the new one to maintain non-overlapping property.

Start from the first interval. Compare it with the next. If they overlap, merge them into one interval. Replace the two intervals with the merged one. Continue until no overlaps remain. For example, [1,3], [2,5], [6,9] -> merge [1,3] and [2,5] to [1,5], final list [1,5], [6,9].

Result

The list is sorted and has no overlapping intervals.

Merging after insertion ensures the list stays clean and ready for further operations.

5

Advanced

Efficient Single-Pass Merge During Insertion

🤔Before reading on: do you think it's possible to insert and merge intervals in one pass? Commit to yes or no.

Concept: Combine insertion and merging in one pass to improve efficiency.

Create a new list. Traverse original intervals: - Add all intervals that end before new interval starts. - Merge all overlapping intervals with the new interval. - Add remaining intervals after new interval ends. Example code snippet: List result = new ArrayList<>(); int i = 0; while (i < intervals.size() && intervals.get(i).end < newInterval.start) { result.add(intervals.get(i++)); } 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++; } result.add(newInterval); while (i < intervals.size()) { result.add(intervals.get(i++)); } return result;

Result

The new interval is inserted and merged in one pass, improving performance.

Knowing this single-pass approach helps write efficient code for large interval lists.

6

Expert

Handling Edge Cases and Interval Boundaries

🤔Before reading on: do you think intervals that just touch at boundaries (e.g., [1,3] and [3,5]) should merge? Commit to yes or no.

Concept: Decide how to treat intervals that touch but do not overlap and handle empty or invalid intervals.

Some systems consider intervals touching at boundaries as overlapping (merge [1,3] and [3,5] to [1,5]). Others treat them as separate. Decide based on requirements. Also, handle cases where new interval is empty (start > end) or list is empty. Validate inputs before processing.

Result

Robust interval insertion that respects business rules and avoids errors.

Understanding boundary conditions prevents subtle bugs and ensures correct interval management.

Under the Hood

The algorithm works by scanning the sorted list once or twice to find the correct insertion point and then merging overlapping intervals by comparing start and end points. Internally, it uses comparisons and list operations to maintain order and merge intervals efficiently.

Why designed this way?

This approach balances simplicity and efficiency. Sorting first allows linear scans instead of complex searches. Merging after insertion avoids repeated reordering. Alternatives like interval trees are more complex and used for dynamic queries, but this method suits static or batch updates.

Intervals list:
┌───────────────┐
│ [1,3] [6,9]  │
└───────────────┘
Insert [2,5]:
Step 1: Find insertion point
  Compare starts: 2 > 1, 2 < 6 -> insert between [1,3] and [6,9]
Step 2: Merge overlaps
  Compare [1,3] and [2,5] -> overlap -> merge to [1,5]
  Compare [1,5] and [6,9] -> no overlap
Final list:
┌───────────────┐
│ [1,5] [6,9]  │
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think intervals that only touch at the boundary should always merge? Commit yes or no.

Common Belief: Intervals that touch at boundaries like [1,3] and [3,5] are always merged.

Reality: Whether to merge touching intervals depends on the problem's definition; some treat them as overlapping, others as separate.

Why it matters: Merging or not merging touching intervals changes the final list and can cause incorrect scheduling or resource allocation.

Quick: Do you think inserting the new interval anywhere and then sorting the whole list is efficient? Commit yes or no.

Common Belief: You can insert the new interval anywhere and then sort the entire list again.

Reality: Sorting the entire list after insertion is less efficient than inserting in order and merging, especially for large lists.

Why it matters: Inefficient sorting increases runtime and can cause performance issues in real-time systems.

Quick: Do you think merging intervals before inserting the new one is better? Commit yes or no.

Common Belief: Merging existing intervals before inserting the new one is necessary.

Reality: Existing intervals are already non-overlapping and sorted; merging before insertion is redundant and wastes time.

Why it matters: Unnecessary merging wastes resources and complicates the algorithm.

Quick: Do you think the new interval can be inserted without checking for overlaps? Commit yes or no.

Common Belief: You can just insert the new interval without merging overlaps.

Reality: Not merging overlaps leads to incorrect interval lists with overlaps, breaking assumptions and causing errors.

Why it matters: Overlapping intervals can cause double bookings or incorrect calculations in scheduling.

Expert Zone

1

Merging intervals in-place can save memory but requires careful index management to avoid skipping intervals.

2

Choosing whether to merge touching intervals depends on domain-specific definitions, such as inclusive or exclusive time ranges.

3

Using binary search to find the insertion point can optimize performance for very large sorted lists.

When NOT to use

This approach is not suitable for highly dynamic interval sets with frequent insertions and deletions; interval trees or segment trees are better alternatives for such cases.

Production Patterns

In production, this pattern is used in calendar apps, booking systems, and network scheduling where intervals are mostly static or batch updated. Efficient single-pass insertion and merge is preferred for performance.

Connections

Merge Sort

Both involve merging sorted sequences efficiently.

Understanding how merge sort combines sorted lists helps grasp why merging intervals after insertion keeps the list sorted and clean.

Database Range Queries

Insert Interval manages ranges similar to how databases index and query range data.

Knowing interval insertion aids in understanding how databases optimize queries over time ranges or numeric intervals.

Project Management Timeline

Managing intervals is like scheduling tasks on a timeline without overlap.

This connection shows how interval insertion algorithms help avoid conflicts in real-world project schedules.

Common Pitfalls

#1 Inserting the new interval at the end without sorting or merging.

Wrong approach:

intervals.add(newInterval);
return intervals;

Correct approach:

Use the insertion and merge algorithm to place and merge the new interval properly.

Root cause:

Misunderstanding that intervals must remain sorted and non-overlapping after insertion.

#2 Merging intervals incorrectly by only comparing start times.

Wrong approach:

if (intervals.get(i).start <= newInterval.start) {
merge intervals;
}

Correct approach:

Check both start and end times to detect overlap: intervals.get(i).start <= newInterval.end && intervals.get(i).end >= newInterval.start

Root cause:

Oversimplifying overlap condition leads to missed merges or incorrect merges.

#3 Not handling empty interval list before insertion.

Wrong approach:

Assuming intervals list is never empty and directly accessing elements.

Correct approach:

Check if intervals list is empty; if yes, return list with only newInterval.

Root cause:

Ignoring edge cases causes runtime errors or incorrect results.

Key Takeaways

Intervals represent ranges and must be managed carefully to avoid overlaps.

Inserting a new interval requires placing it in order and merging overlaps to keep the list sorted and clean.

Efficient algorithms combine insertion and merging in one pass for better performance.

Handling edge cases like touching intervals and empty lists is crucial for robust solutions.

This concept is foundational for scheduling, booking, and range query systems in real-world applications.

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