Insert Interval into Sorted List in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the insertion index.

DSA C

int index = [1];

Drag options to blanks, or click blank then click option'

Aintervals[0].end

BnewInterval.end

Cintervals[0].start

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using the end value instead of index.

Initializing with interval values which may not be correct.

The insertion index should be initialized to 0 to start traversing from the beginning of the sorted list.

2fill in blank

medium

Complete the code to check if the current interval ends before the new interval starts.

DSA C

if (intervals[i].end < [1]) {

Drag options to blanks, or click blank then click option'

AnewInterval.start

BnewInterval.end

Cintervals[i].start

Dintervals[i].end

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with newInterval.end instead of newInterval.start.

Using the start of the current interval instead of the end.

We check if the current interval ends before the new interval starts to decide if they do not overlap.

3fill in blank

hard

Fix the error in merging intervals by completing the code to update the new interval's end value.

DSA C

if (intervals[i].start <= newInterval.end) {
    newInterval.end = [1] > newInterval.end ? [1] : newInterval.end;
}

Drag options to blanks, or click blank then click option'

Aintervals[i].end

Bintervals[i].start

CnewInterval.start

DnewInterval.start + intervals[i].end

Attempts:

3 left

💡 Hint

Common Mistakes

Using the start value instead of the end value.

Adding start and end values incorrectly.

When merging, the new interval's end should be the maximum of its current end and the current interval's end.

4fill in blank

hard

Fill both blanks to correctly insert the new interval into the result list.

DSA C

result[[1]] = newInterval;
return [2];

Drag options to blanks, or click blank then click option'

Aindex

Bindex + 1

Cresult

Dresult + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Returning the index instead of the result array.

Using incorrect index values for insertion.

The new interval is inserted at the current index, and the updated result array is returned.

5fill in blank

hard

Fill all three blanks to complete the loop that merges overlapping intervals.

DSA C

for (int i = 0; i [1] intervalsSize; i++) {
    if (intervals[i].start > newInterval.end) {
        result[[2]] = newInterval;
        [3];
    }
    // merging logic
}

Drag options to blanks, or click blank then click option'

A<

Bindex

Creturn result

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= in the loop condition causing out-of-bounds errors.

Not returning the result after insertion.

The loop runs while i is less than intervalsSize, inserts newInterval at index, then returns the result.

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