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.