Insert Interval into Sorted List in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting an interval with overlap

What is the output list of intervals after inserting [4, 8] into the sorted list [[1, 3], [6, 9]]?

DSA C

intervals = [[1, 3], [6, 9]]
newInterval = [4, 8]

// After insertion and merging overlapping intervals, print the resulting list

A [[1, 3], [4, 9]]

B [[1, 8], [9, 9]]

C [[1, 9]]

D [[1, 3], [6, 8]]

💡 Hint

Remember to merge intervals that overlap after insertion.

The new interval [4, 8] overlaps with [6, 9], so they merge into [4, 9]. Also, [1, 3] does not overlap with [4, 9], so the final list is [[1, 3], [4, 9]].

❓ Predict Output

intermediate

Result after inserting a non-overlapping interval

What is the output list of intervals after inserting [10, 12] into the sorted list [[1, 5], [6, 9]]?

DSA C

intervals = [[1, 5], [6, 9]]
newInterval = [10, 12]

// Insert and print the resulting list

A [[1, 12]]

B [[1, 5], [6, 9], [10, 12]]

C [[1, 5], [6, 12]]

D [[10, 12], [1, 5], [6, 9]]

💡 Hint

Check if the new interval overlaps with any existing intervals.

The new interval [10, 12] does not overlap with any existing intervals, so it is simply added at the end.

🔧 Debug

advanced

Identify the error in interval insertion code

What error will this code produce when inserting [2, 5] into [[1, 3], [6, 9]]? int intervals[][2] = {{1, 3}, {6, 9}}; int newInterval[2] = {2, 5}; int result[3][2]; int idx = 0; for (int i = 0; i < 2; i++) { if (intervals[i][1] < newInterval[0]) { result[idx][0] = intervals[i][0]; result[idx][1] = intervals[i][1]; idx++; } else if (intervals[i][0] > newInterval[1]) { result[idx][0] = newInterval[0]; result[idx][1] = newInterval[1]; idx++; newInterval[0] = intervals[i][0]; newInterval[1] = intervals[i][1]; } else { newInterval[0] = (intervals[i][0] < newInterval[0]) ? intervals[i][0] : newInterval[0]; newInterval[1] = (intervals[i][1] > newInterval[1]) ? intervals[i][1] : newInterval[1]; } } result[idx][0] = newInterval[0]; result[idx][1] = newInterval[1]; idx++; // print result

DSA C

int intervals[][2] = {{1, 3}, {6, 9}};
int newInterval[2] = {2, 5};
int result[3][2];
int idx = 0;
for (int i = 0; i < 2; i++) {
  if (intervals[i][1] < newInterval[0]) {
    result[idx][0] = intervals[i][0];
    result[idx][1] = intervals[i][1];
    idx++;
  } else if (intervals[i][0] > newInterval[1]) {
    result[idx][0] = newInterval[0];
    result[idx][1] = newInterval[1];
    idx++;
    newInterval[0] = intervals[i][0];
    newInterval[1] = intervals[i][1];
  } else {
    newInterval[0] = (intervals[i][0] < newInterval[0]) ? intervals[i][0] : newInterval[0];
    newInterval[1] = (intervals[i][1] > newInterval[1]) ? intervals[i][1] : newInterval[1];
  }
}
result[idx][0] = newInterval[0];
result[idx][1] = newInterval[1];
idx++;

A Compilation error: cannot assign arrays directly

B Runtime error: index out of bounds

C Logical error: newInterval inserted multiple times

D No error, code runs correctly

💡 Hint

In C, arrays cannot be assigned directly with = operator.

In C, you cannot assign arrays directly like result[idx++] = intervals[i]; This causes a compilation error.

🧠 Conceptual

advanced

Understanding interval merging logic

Why is it important to sort intervals before inserting a new interval and merging?

A Sorting reduces the number of intervals to merge by removing duplicates.

B Sorting is not necessary; intervals can be merged in any order.

C Sorting helps to find the maximum interval length quickly.

D Sorting ensures intervals are in order, so merging adjacent or overlapping intervals is easier and correct.

💡 Hint

Think about how merging works when intervals are ordered.

When intervals are sorted by start time, we can merge overlapping intervals in one pass from left to right. Without sorting, merging is complicated and may miss overlaps.

🚀 Application

expert

Final merged intervals after multiple insertions

Given the initial sorted intervals [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], what is the final list after inserting intervals [4, 8] and then [17, 19] sequentially with merging?

A [[1, 2], [3, 10], [12, 19]]

B [[1, 2], [3, 8], [6, 10], [12, 16], [17, 19]]

C [[1, 2], [3, 10], [12, 16], [17, 19]]

D [[1, 2], [3, 5], [6, 10], [12, 16], [17, 19]]

💡 Hint

Merge overlapping intervals after each insertion carefully.

Inserting [4, 8] merges with [3, 5], [6, 7], and [8, 10] into [3, 10]. Then inserting [17, 19] adds a new interval at the end.

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