Insert Interval into Sorted List in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal when inserting an interval into a sorted list of intervals?

To add the new interval into the correct position in the list and merge any overlapping intervals to keep the list sorted and non-overlapping.

beginner

How do you determine if two intervals overlap?

Two intervals overlap if the start of one interval is less than or equal to the end of the other interval, and the start of the other interval is less than or equal to the end of the first interval.

intermediate

Why is it important to keep the list of intervals sorted after insertion?

Keeping the list sorted helps efficiently find where to insert new intervals and makes merging overlapping intervals easier and faster.

intermediate

What is the time complexity of inserting an interval into a sorted list and merging overlaps?

The time complexity is O(n), where n is the number of intervals, because you may need to check and merge intervals across the entire list.

beginner

In C, what data structure is commonly used to represent an interval for this problem?

A struct with two integer fields, usually named start and end, to represent the beginning and end of the interval.

What should you do first when inserting a new interval into a sorted list?

A Merge all intervals first

B Find the correct position to insert the new interval

C Delete overlapping intervals

D Sort the list again

You first find where the new interval fits in the sorted list before merging overlaps.

When do two intervals NOT overlap?

A When one interval is inside the other

B When they share a boundary point

C When one interval ends before the other starts

D When they have the same start

Intervals do not overlap if one ends before the other begins.

What is the result after merging overlapping intervals?

A A list with no overlapping intervals

B A list with all intervals doubled

C A list sorted in descending order

D A list with only the new interval

Merging removes overlaps so the list has only non-overlapping intervals.

Which data structure is best to store intervals for this problem in C?

A String array

B Linked list of integers

C Single integer variable

D Array of structs with start and end fields

An array of structs holding start and end values is ideal for intervals.

What is the main challenge when inserting an interval into a sorted list?

A Merging overlapping intervals correctly

B Finding the maximum interval

C Sorting the list in reverse

D Deleting all intervals

The key challenge is merging any intervals that overlap with the new one.

Explain step-by-step how to insert a new interval into a sorted list of intervals and merge overlaps.

Think about scanning the list from start to end and handling intervals in three parts.

Describe how you check if two intervals overlap and how to merge them.

Overlap means intervals touch or cross; merging combines their ranges.

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