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 list while current.end < new.start

↓

Check overlap with current interval

Yes No↓

Merge intervals

↓

Adjust pointers

↓

Continue merging if needed

↓

Finish insertion

Create a new interval node, traverse the sorted list to find the correct position, merge overlapping intervals, and insert the new or merged interval maintaining sorted order.

Execution Sample

DSA C

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

// Insert new interval into sorted list with merging

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

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Create new interval [4, 9]	N/A	new = [4,9]->NULL	[1,3]->[6,7]->[8,10]->[12,16]->NULL
2	Start at head	[1,3]	current = head	[1,3]->[6,7]->[8,10]->[12,16]->NULL
3	Check if current.end < new.start (3 < 4)	current=[1,3]	Move prev=current, current=current.next	prev=[1,3], current=[6,7]
4	Check if current.end < new.start (7 < 4)	current=[6,7]	Condition false, stop traversal	prev=[1,3], current=[6,7]
5	Check overlap: new.start <= current.end (4 <= 7)	current=[6,7]	Merge: new.start = min(4,6)=4, new.end = max(9,7)=9	new=[4,9]
6	Remove current [6,7] from list	current=[6,7]	prev.next = current.next ([8,10])	List: [1,3]->[8,10]->[12,16]
7	Check next node [8,10] overlap with new [4,9]	current=[8,10]	Overlap: merge new.end = max(9,10)=10	new=[4,10]
8	Remove current [8,10]	current=[8,10]	prev.next = current.next ([12,16])	List: [1,3]->[12,16]
9	Check next node [12,16] overlap with new [4,10]	current=[12,16]	No overlap (12 > 10), stop merging	List: [1,3]->[12,16]
10	Insert merged new interval after prev	prev=[1,3]	new.next = prev.next; prev.next = new	List: [1,3]->[4,10]->[12,16]
11	Insertion complete	N/A	N/A	[1,3]->[4,10]->[12,16]->NULL

💡 Traversal stops when no more overlapping intervals are found and new interval is inserted.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 6	After Step 8	After Step 10	Final
current	[1,3]	[6,7]	[6,7]	[8,10]	[12,16]	[12,16]	NULL
prev	NULL	[1,3]	[1,3]	[1,3]	[1,3]	[1,3]	[1,3]
new	Created [4,9]	[4,9]	[4,9]	[4,9]	[4,10]	[4,10]	[4,10]
List	[1,3]->[6,7]->[8,10]->[12,16]	[1,3]->[6,7]->[8,10]->[12,16]	[1,3]->[6,7]->[8,10]->[12,16]	[1,3]->[8,10]->[12,16]	[1,3]->[12,16]	[1,3]->[4,10]->[12,16]	[1,3]->[4,10]->[12,16]

Key Moments - 3 Insights

Why do we move 'prev' and 'current' pointers during traversal?

We move 'prev' and 'current' to find the correct position where the new interval fits without overlap. See execution_table steps 3 and 4 where 'prev' points to [1,3] and 'current' moves forward.

How do we merge overlapping intervals?

When intervals overlap, we update the new interval's start to the minimum start and end to the maximum end, removing the overlapping node from the list. See steps 5, 7, and 8 in the execution_table.

Why do we insert the new interval after 'prev'?

Because 'prev' points to the last interval before the new merged interval, inserting after 'prev' keeps the list sorted. See step 10 where new is linked after 'prev'.

Visual Quiz - 3 Questions

Look at the execution_table, what is the 'new' interval after step 7?

A [4,9]

B [4,10]

C [6,7]

D [8,10]

💡 Hint

Check the 'new' variable value in execution_table row 7 where merging with [8,10] happens.

At which step does the traversal stop because there is no overlap with the next node?

A Step 4

B Step 6

C Step 9

D Step 10

💡 Hint

Look at execution_table step 9 where the next node [12,16] does not overlap with new [4,10].

If the new interval was [5,6] instead of [4,9], how would the list look after insertion?

A [1,3]->[5,7]->[8,10]->[12,16]

B [1,3]->[4,10]->[12,16]

C [1,3]->[5,6]->[6,7]->[8,10]->[12,16]

D ]61,21[>-]01,8[>-]7,5[>-]3,1[

💡 Hint

Consider merging [5,6] with overlapping intervals [6,7] and [8,10] as in the variable_tracker.

Concept Snapshot

Insert Interval into Sorted List:
- Traverse list until current.end < new.start
- Merge overlapping intervals by updating new.start and new.end
- Remove merged intervals from list
- Insert merged new interval after prev
- Maintains sorted order and merges overlaps
- Handles empty list or no overlap cases

Full Transcript

This concept shows how to insert a new interval into a sorted linked list of intervals. We create a new interval node, then traverse the list to find where it fits. While traversing, we move pointers 'prev' and 'current' to find the correct position. If intervals overlap, we merge by updating the new interval's start and end to cover all overlaps, removing the old overlapping nodes. Finally, we insert the merged interval after 'prev' to keep the list sorted. The execution table tracks each step, pointer changes, and the list's visual state. Key moments clarify why pointers move, how merging works, and why insertion happens after 'prev'. The visual quiz tests understanding of these steps and changes. This method ensures the list remains sorted and merged after insertion.

Practice

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

easy

A. Sort the list again after insertion without merging

B. Add the new interval at the end without merging

C. Remove all intervals that come before the new interval

D. Merge overlapping intervals and keep the list sorted

Solution

1. Step 1: Understand the problem context

   The list contains sorted, non-overlapping intervals. Inserting a new interval may cause overlaps.

2. Step 2: Determine the correct insertion approach

   We must merge any overlapping intervals with the new one and keep the list sorted to maintain the property.

3. Final Answer:

   Merge overlapping intervals and keep the list sorted -> Option D

4. Quick Check:

   Insert interval = merge + sort [OK]

Hint: Always merge overlaps to keep intervals sorted and non-overlapping [OK]

Common Mistakes:

• Inserting without merging causes overlaps
• Appending at the end breaks sorting
• Removing intervals unnecessarily

2. Which of the following C code snippets correctly declares a structure for an interval with start and end integers?

easy

A. typedef struct Interval { int start; int end; } Interval;

B. struct Interval { int start; int end; };

C. struct { int start; int end; } Interval;

D. typedef struct Interval { int start; int end; };

Solution

1. Step 1: Understand C struct typedef syntax

   To define a struct and typedef it simultaneously, use: typedef struct Name { ... } Name;

2. Step 2: Match the correct syntax

   typedef struct Interval { int start; int end; } Interval; uses typedef struct Interval { int start; int end; } Interval; which is correct.

3. Final Answer:

   typedef struct Interval { int start; int end; } Interval; -> Option A

4. Quick Check:

   typedef struct Name { ... } Name; = typedef struct Interval { int start; int end; } Interval; [OK]

Hint: Use typedef struct Name { ... } Name; for clean interval type [OK]

Common Mistakes:

• Missing typedef keyword
• Incorrect struct declaration without name
• Declaring variable instead of type

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,5], [6,9]]

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

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

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

Solution

1. Step 1: Identify overlapping intervals

   The new interval [2,5] overlaps with [1,3] because 2 ≤ 3.

2. Step 2: Merge overlapping intervals

   Merge [1,3] and [2,5] into [1,5]. The interval [6,9] remains unchanged.

3. Final Answer:

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

4. Quick Check:

   Merge [1,3] & [2,5] = [1,5] [OK]

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

Common Mistakes:

• Not merging overlapping intervals
• Inserting new interval without sorting
• Appending new interval at wrong position

4. Consider this buggy C code snippet to insert an interval into a sorted list. What is the main error?

void insertInterval(Interval* intervals, int* size, Interval newInterval) {
    int i = 0;
    while (i < *size && intervals[i].end < newInterval.start) {
        i++;
    }
    intervals[i] = newInterval; // Bug here
    (*size)++;
}

medium

A. Increments size before insertion

B. Does not check for overlapping intervals

C. Overwrites an existing interval without shifting elements

D. Uses wrong comparison operator in while loop

Solution

1. Step 1: Analyze insertion logic

   The code finds position i but directly overwrites intervals[i] without moving later intervals.

2. Step 2: Identify the error impact

   Overwriting causes loss of data and corrupts the list. Proper insertion requires shifting elements right.

3. Final Answer:

   Overwrites an existing interval without shifting elements -> Option C

4. Quick Check:

   Overwrite without shift = data loss [OK]

Hint: Shift elements right before inserting new interval [OK]

Common Mistakes:

• Ignoring element shifting
• Not handling overlaps
• Incorrect loop conditions

5. You have intervals [[1,2], [3,5], [6,7], [8,10], [12,16]] and want to insert [4,8]. What is the final list after insertion and merging?

hard

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

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

C. [[1,2], [3,5], [4,8], [6,7], [8,10], [12,16]]

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

Solution

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

   Intervals [3,5], [6,7], and [8,10] overlap with [4,8].

2. Step 2: Merge all overlapping intervals

   Merge [3,5], [6,7], [8,10], and [4,8] into [3,10].

3. Step 3: Construct final list

   Keep [1,2] and [12,16] unchanged. Final list: [[1,2], [3,10], [12,16]].

4. Final Answer:

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

5. Quick Check:

   Merge overlapping intervals = [3,10] [OK]

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

Common Mistakes:

• Not merging all overlapping intervals
• Inserting without merging
• Removing intervals incorrectly