Insert Interval into Sorted List in DSA C++ - Execution Trace

Concept Flow - Insert Interval into Sorted List

Create new interval node

↓

Start at head of sorted list

↓

Traverse nodes while current.end < new.start

↓

Check if current overlaps with new interval

↓

Merge intervals

↓

Continue merging if next nodes overlap

↓

Link merged interval to rest of list

↓

Return updated list head

We create a new interval node, traverse the sorted list to find the right place, merge overlapping intervals, and insert the new or merged interval maintaining sorted order.

Execution Sample

DSA C++

struct Interval {
  int start, end;
  Interval* next;
};

Interval* insertInterval(Interval* head, Interval* newInterval) {
  // Insert newInterval into sorted list merging overlaps
}

This code inserts a new interval into a sorted linked list of intervals, merging any overlapping intervals.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Create new interval [4,7]	None	newInterval points to [4,7]	[1,3] -> [6,9] -> [12,16] -> null newInterval: [4,7]
2	Start at head [1,3]	[1,3]	current = head	[1,3] -> [6,9] -> [12,16] -> null newInterval: [4,7]
3	Check if current.end < newInterval.start (3 < 4)	[1,3]	Move prev to current, current to next	prev: [1,3] current: [6,9] List: [1,3] -> [6,9] -> [12,16] -> null
4	Check if current.end < newInterval.start (9 < 4) false	[6,9]	Stop traversal	prev: [1,3] current: [6,9] newInterval: [4,7]
5	Check overlap: current.start <= newInterval.end (6 <= 7) true	[6,9]	Merge intervals: newInterval.start = min(4,6)=4, newInterval.end = max(7,9)=9	newInterval updated to [4,9]
6	Move current to next [12,16]	[12,16]	current = current.next	prev: [1,3] current: [12,16] newInterval: [4,9]
7	Check overlap: current.start <= newInterval.end (12 <= 9) false	[12,16]	Stop merging	prev: [1,3] current: [12,16] newInterval: [4,9]
8	Link prev.next to newInterval	prev: [1,3]	prev.next = newInterval	List: [1,3] -> [4,9]
9	Link newInterval.next to current	newInterval: [4,9]	newInterval.next = current	List: [1,3] -> [4,9] -> [12,16] -> null
10	Return head	head: [1,3]	No pointer changes	Final List: [1,3] -> [4,9] -> [12,16] -> null

💡 Traversal stops when current interval does not overlap with newInterval and insertion is done.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
current	[1,3]	[6,9]	[6,9]	[12,16]	[12,16]
prev	null	[1,3]	[1,3]	[1,3]	[1,3]
newInterval	null	[4,7]	[4,9]	[4,9]	[4,9]
head	[1,3]	[1,3]	[1,3]	[1,3]	[1,3]

Key Moments - 3 Insights

Why do we move 'prev' and 'current' pointers while current.end < newInterval.start?

Because intervals before newInterval do not overlap, we move forward to find the correct insertion point. See execution_table step 3 where traversal moves past [1,3].

How do we merge overlapping intervals?

We update newInterval's start to the minimum start and end to the maximum end of overlapping intervals. See step 5 where newInterval [4,7] merges with [6,9] to become [4,9].

Why do we link prev.next to newInterval and newInterval.next to current?

To insert the merged interval into the list maintaining order and connect the rest of the list. See steps 8 and 9 for pointer updates.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of newInterval after step 5?

A [4,9]

B [4,7]

C [6,9]

D [1,3]

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 5 in execution_table.

At which step does the traversal stop because current interval does not overlap with newInterval?

A Step 3

B Step 4

C Step 7

D Step 9

💡 Hint

Look for the step where overlap check is false and merging stops in execution_table.

If the newInterval was [10,11], where would it be inserted?

A Before [1,3]

B Between [6,9] and [12,16]

C After [12,16]

D Merged with [6,9]

💡 Hint

Consider the traversal and overlap logic shown in execution_table and variable_tracker.

Concept Snapshot

Insert Interval into Sorted List:
- Traverse list while current.end < new.start
- Merge overlapping intervals by updating newInterval
- Insert merged interval by linking prev.next and newInterval.next
- Maintain sorted order and no overlaps
- Return updated head of list

Full Transcript

This concept shows how to insert a new interval into a sorted linked list of intervals. We start by creating the new interval node. Then we traverse the list until we find intervals that do not overlap with the new one. We merge any overlapping intervals by updating the start and end of the new interval. After merging, we insert the new or merged interval into the list by adjusting pointers. The final list remains sorted and without overlapping intervals.

Practice

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

easy

A. To merge overlapping intervals and keep the list sorted

B. To add the new interval at the end without merging

C. To remove all intervals that come before the new interval

D. To sort the intervals again after insertion without merging

Solution

1. Step 1: Understand the problem context

   We have a sorted list of intervals that do not overlap. When inserting a new interval, we must keep the list sorted and merge any overlapping intervals.

2. Step 2: Identify the correct approach

   Simply adding the new interval without merging can cause overlaps. Sorting again without merging breaks the non-overlapping property. Removing intervals before the new one is incorrect.

3. Final Answer:

   To merge overlapping intervals and keep the list sorted -> Option A

4. Quick Check:

   Insert Interval = Merge and keep sorted [OK]

Hint: Always merge overlapping intervals after insertion [OK]

Common Mistakes:

• Inserting without merging overlaps
• Sorting intervals again without merging
• Removing intervals unnecessarily

2. Which of the following C++ code snippets correctly declares a vector of intervals where each interval is a pair of integers?

easy

A. std::vector intervals;

B. std::vector intervals;

C. std::vector intervals;

D. std::vector> intervals;

Solution

1. Step 1: Understand vector and pair syntax

   In C++, a vector of pairs is declared as std::vector>. The pair must specify both types inside angle brackets.

2. Step 2: Check each option

   std::vector> intervals; correctly uses std::pair. std::vector intervals; is invalid syntax for vector. std::vector intervals; misses the second type in pair. std::vector intervals; misses template parameters for pair.

3. Final Answer:

   std::vector> intervals; -> Option D

4. Quick Check:

   Vector of pairs syntax = std::vector> intervals; [OK]

Hint: Use std::vector> for intervals [OK]

Common Mistakes:

• Missing template parameters in pair
• Incorrect vector declaration syntax
• Using incomplete pair types

3. Given the sorted intervals [(1, 3), (6, 9)] and a new interval (2, 5), what will be the resulting list after insertion and merging?

medium

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

B. [(1, 5), (6, 9)]

C. [(2, 5), (6, 9)]

D. [(1, 9)]

Solution

1. Step 1: Identify overlapping intervals

   The new interval (2, 5) overlaps with (1, 3) because 2 <= 3. They should be merged into (1, 5).

2. Step 2: Merge and keep other intervals

   After merging (1, 3) and (2, 5) into (1, 5), the interval (6, 9) remains unchanged.

3. Final Answer:

   [(1, 5), (6, 9)] -> Option B

4. Quick Check:

   Merge overlapping intervals = [(1, 5), (6, 9)] [OK]

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

Common Mistakes:

• Not merging overlapping intervals
• Inserting without sorting
• Merging all intervals incorrectly

4. Consider the following C++ code snippet for inserting an interval into a sorted list of intervals:

std::vector> insertInterval(std::vector>& intervals, std::pair newInterval) {
    std::vector> result;
    int i = 0;
    while (i < intervals.size() && intervals[i].second < newInterval.first) {
        result.push_back(intervals[i]);
        i++;
    }
    while (i < intervals.size() && intervals[i].first <= newInterval.second) {
        newInterval.first = std::min(newInterval.first, intervals[i].first);
        newInterval.second = std::max(newInterval.second, intervals[i].second);
        i++;
    }
    result.push_back(newInterval);
    while (i < intervals.size()) {
        result.push_back(intervals[i]);
        i++;
    }
    return result;
}

What is the bug in this code if any?

medium

A. No bug; the code correctly inserts and merges intervals

B. The first while loop condition should use <= instead of <

C. The second while loop should check intervals[i].second instead of intervals[i].first

D. The newInterval is not pushed back at the correct position

Solution

1. Step 1: Analyze the first while loop

   The first loop adds all intervals that end before the new interval starts, correctly skipping non-overlapping intervals before newInterval.

2. Step 2: Analyze the second while loop

   The second loop merges all intervals overlapping with newInterval by updating its start and end correctly.

3. Step 3: Analyze the final steps

   After merging, newInterval is added, then remaining intervals are appended. This maintains sorted order and merges properly.

4. Final Answer:

   No bug; the code correctly inserts and merges intervals -> Option A

5. Quick Check:

   Code logic matches insert and merge steps [OK]

Hint: Check loop conditions carefully for overlap and order [OK]

Common Mistakes:

• Changing loop conditions incorrectly
• Pushing newInterval too early or late
• Merging intervals incorrectly

5. You have a sorted list of intervals: [(1, 2), (3, 5), (6, 7), (8, 10), (12, 16)]. You want to insert a new interval (4, 8). What is the final list after insertion and merging?

hard

A. [(1, 2), (3, 5), (4, 8), (6, 7), (8, 10), (12, 16)]

B. [(1, 2), (4, 10), (12, 16)]

C. [(1, 2), (3, 10), (12, 16)]

D. [(1, 2), (3, 8), (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 all overlapping intervals

   Merge (3, 5), (6, 7), (8, 10), and (4, 8) into one interval. The merged interval starts at min(3,4,6,8) = 3 and ends at max(5,7,8,10) = 10.

3. Step 3: Keep non-overlapping intervals

   Intervals (1, 2) and (12, 16) remain unchanged.

4. Final Answer:

   [(1, 2), (3, 10), (12, 16)] -> Option C

5. Quick Check:

   Merge overlapping intervals = [(1, 2), (3, 10), (12, 16)] [OK]

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

Common Mistakes:

• Not merging all overlapping intervals
• Inserting new interval without merging
• Incorrect interval boundaries after merge