Insert Interval into Sorted List in DSA C - Deep Dive

Overview - Insert Interval into Sorted List

What is it?

Insert Interval into Sorted List means adding a new time range into a list of existing time ranges that are sorted and do not overlap. The goal is to place the new interval correctly and merge any overlapping intervals so the list stays sorted and clean. This helps manage schedules, bookings, or any timeline data efficiently.

Why it matters

Without this, managing overlapping time ranges would be messy and error-prone. For example, if you book meeting rooms or plan events, you need to know when times overlap and merge them to avoid conflicts. This concept keeps data organized and easy to understand, saving time and preventing mistakes.

Where it fits

Before this, you should understand arrays or lists and how sorting works. After this, you can learn about interval trees or advanced scheduling algorithms that handle more complex queries efficiently.

Mental Model

Core Idea

Insert the new interval by finding where it fits, then merge any overlapping intervals to keep the list sorted and non-overlapping.

Think of it like...

Imagine you have a row of books sorted by their height. You want to add a new book in the right spot and if it overlaps with others (like a book that is too wide), you combine them into one bigger book so the row stays neat.

Sorted intervals list:
┌─────────┬─────────┬─────────┐
│ [1,3]   │ [6,9]   │ [12,15] │
└─────────┴─────────┴─────────┘

New interval: [2,7]

Step 1: Find position to insert
Step 2: Merge overlapping intervals

Result:
┌───────────────┬─────────┐
│ [1,9]         │ [12,15] │
└───────────────┴─────────┘

Build-Up - 7 Steps

1

Foundation

Understanding Intervals and Sorting

Concept: Intervals are pairs of numbers representing ranges, and sorting means arranging them by start time.

An interval is like a time slot with a start and end, for example [1,3]. A sorted list of intervals means each interval starts after the previous one ends or at least does not start before it. For example, [1,3], [6,9], [12,15] is sorted because 6 > 3 and 12 > 9.

Result

You can quickly find where a new interval might fit by comparing start times.

Understanding intervals and sorting is the base for inserting and merging intervals efficiently.

2

Foundation

What Does Overlapping Mean?

Concept: Two intervals overlap if they share any common points in their ranges.

For example, [1,3] and [2,5] overlap because 2 and 3 are in both intervals. But [1,3] and [4,6] do not overlap because 4 is after 3. Overlapping intervals need to be merged to avoid confusion.

Result

You know when to merge intervals after insertion.

Recognizing overlap is key to keeping the list clean and non-overlapping.

3

Intermediate

Finding Insert Position in Sorted List

🤔Before reading on: do you think you should insert the new interval before the first interval that starts after it, or after all intervals?

Concept: Locate the first interval whose start is greater than the new interval's start to find where to insert.

Since the list is sorted by start times, scan from left to right until you find an interval starting after the new interval. Insert the new interval just before that. If none found, append at the end.

Result

The new interval is placed in the correct order, preserving sorting.

Knowing how to find the insert position avoids unnecessary sorting after insertion.

4

Intermediate

Merging Overlapping Intervals After Insert

🤔Before reading on: do you think merging should happen only with the new interval or with all intervals in the list?

Concept: After inserting, merge intervals that overlap with the new one to keep the list non-overlapping.

Check intervals before and after the inserted interval. If they overlap with the new interval, merge by taking the smallest start and largest end among them. Remove merged intervals and replace with the merged one.

Result

The list remains sorted and has no overlapping intervals.

Merging after insertion ensures the list stays clean and usable for further operations.

5

Intermediate

Handling Edge Cases in Interval Insertion

🤔Before reading on: do you think an interval that touches another at the boundary counts as overlapping?

Concept: Intervals that touch at boundaries (e.g., end of one is start of another) are considered overlapping and should merge.

For example, [1,3] and [3,5] share the point 3, so they merge into [1,5]. This prevents gaps that are not meaningful in scheduling contexts.

Result

Intervals that touch merge correctly, avoiding false gaps.

Understanding boundary merging prevents subtle bugs in interval management.

6

Advanced

Efficient Single-Pass Insertion and Merge

🤔Before reading on: do you think you need multiple passes to insert and merge, or can it be done in one pass?

Concept: You can insert and merge intervals in one pass by scanning and building a new list.

Start scanning intervals: - Add all intervals ending before new interval starts. - Merge overlapping intervals with new interval. - Add remaining intervals after merging. This avoids multiple scans and extra sorting.

Result

Insertion and merging happen efficiently in O(n) time with one pass.

Knowing the one-pass method improves performance and simplifies code.

7

Expert

Memory and In-Place Modification Considerations

🤔Before reading on: do you think modifying the original list in-place is always better than creating a new list?

Concept: In-place modification saves memory but requires careful index management to avoid errors.

When modifying the original list, you must shift intervals and remove merged ones carefully. This avoids extra memory but can be tricky. Creating a new list is safer but uses more memory.

Result

Choosing between in-place and new list depends on memory constraints and code complexity.

Understanding trade-offs between memory and complexity helps write robust production code.

Under the Hood

The algorithm scans the sorted list once, comparing each interval's start and end with the new interval. It uses comparisons to decide whether to add intervals directly, merge them, or skip them. Internally, merging updates the start to the minimum and end to the maximum of overlapping intervals. This process relies on the sorted property to avoid backtracking.

Why designed this way?

Sorting intervals first allows linear-time insertion and merging. Without sorting, merging would require more complex data structures or multiple passes. The design balances simplicity and efficiency, making it practical for many real-world scheduling problems.

Intervals list scanning flow:

Start
  │
  ▼
[Interval i] ──> Compare with new interval
  │               ├─ If ends before new start: add to result
  │               ├─ If overlaps: merge
  │               └─ If starts after new end: add new interval, then rest
  ▼
Repeat for all intervals
  │
  ▼
End with merged list

Myth Busters - 4 Common Misconceptions

Quick: Do intervals that only touch at a boundary count as overlapping? Commit yes or no.

Common Belief: Intervals that only touch at a boundary, like [1,3] and [3,5], are separate and should not merge.

Reality: Intervals touching at boundaries are considered overlapping and should merge into [1,5].

Why it matters: Not merging touching intervals causes false gaps, leading to incorrect scheduling or resource allocation.

Quick: Is it necessary to sort the list again after inserting a new interval? Commit yes or no.

Common Belief: After inserting a new interval, you must sort the entire list again to maintain order.

Reality: If the list is initially sorted, you can insert the new interval in the correct position without full sorting.

Why it matters: Sorting again wastes time and resources; knowing this improves efficiency.

Quick: Can you merge intervals without checking all intervals in the list? Commit yes or no.

Common Belief: You only need to check intervals adjacent to the inserted interval for merging.

Reality: Because the list is sorted, only intervals overlapping or adjacent to the new interval need merging; others remain untouched.

Why it matters: Checking all intervals unnecessarily slows down the algorithm.

Quick: Does merging intervals always reduce the number of intervals in the list? Commit yes or no.

Common Belief: Merging intervals always reduces the total number of intervals.

Reality: Sometimes the new interval does not overlap any existing intervals, so the count increases by one.

Why it matters: Assuming merging always reduces count can cause logic errors in handling the list size.

Expert Zone

1

Merging intervals that touch at boundaries is context-dependent; some applications treat touching intervals as separate.

2

In-place modification requires careful index tracking to avoid skipping or duplicating intervals during merges.

3

The one-pass insertion and merge algorithm leverages the sorted property to guarantee linear time complexity.

When NOT to use

This approach is not suitable when intervals are unsorted or when frequent insertions and deletions happen; interval trees or segment trees are better alternatives for dynamic interval management.

Production Patterns

Used in calendar apps to manage event times, booking systems to handle reservations, and network scheduling to allocate time slots without conflicts.

Connections

Merge Intervals

Insert Interval builds on the Merge Intervals concept by adding a new interval before merging.

Understanding how to merge intervals is essential before learning how to insert and merge efficiently.

Binary Search

Binary search can optimize finding the insert position in a sorted list of intervals.

Applying binary search reduces the search time from linear to logarithmic, improving performance on large lists.

Project Management Scheduling

Insert Interval algorithms help manage task timelines and resource allocation in project management.

Knowing interval insertion helps understand how software tools prevent scheduling conflicts and optimize timelines.

Common Pitfalls

#1 Not merging intervals that touch at boundaries.

Wrong approach:

Intervals: [1,3], [3,5]
After insertion: [1,3], [3,5] (no merge)

Correct approach:

Intervals: [1,3], [3,5]
After insertion and merge: [1,5]

Root cause:

Misunderstanding that touching intervals count as overlapping.

#2 Inserting new interval without finding correct position.

Wrong approach:

Append new interval at the end regardless of order, e.g., [1,3], [6,9], [2,5]

Correct approach:

Insert new interval at correct position to maintain sorting, e.g., [1,3], [2,5], [6,9]

Root cause:

Ignoring the sorted property of the list.

#3 Merging intervals multiple times or missing merges.

Wrong approach:

Merge only with one adjacent interval, missing others, e.g., merging [2,7] with [6,9] but not with [1,3]

Correct approach:

Merge with all overlapping intervals to form [1,9]

Root cause:

Not checking all intervals overlapping with the new interval.

Key Takeaways

Intervals represent ranges and must be managed carefully to avoid overlaps and maintain order.

Inserting a new interval requires finding the correct position and merging overlapping intervals to keep the list clean.

Intervals that touch at boundaries are considered overlapping and should be merged to prevent false gaps.

Efficient insertion and merging can be done in one pass by leveraging the sorted property of the list.

Understanding trade-offs between in-place modification and creating new lists helps write better code.

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