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 or segment into a list of existing non-overlapping, sorted intervals. The goal is to keep the list sorted and merge any overlapping intervals after insertion. This helps manage ranges efficiently, like booking times or reserved spaces.

Why it matters

Without this, managing overlapping time slots or ranges would be messy and error-prone. For example, scheduling meetings or allocating memory would become complicated if intervals overlapped or were unsorted. This concept keeps data clean and easy to query.

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 range queries for faster searching and updates.

Mental Model

Core Idea

Insert the new interval into the right place in the sorted list and merge any intervals that overlap to keep the list clean and sorted.

Think of it like...

Imagine you have a row of non-overlapping books on a shelf sorted by their width. You want to add a new book, but if it overlaps with existing books, you merge them into a bigger book so the shelf stays neat.

Sorted intervals:  ┌─────┐ ┌───────┐ ┌─────┐
                   | 1-3 | | 6-9   | | 12-15|
                   └─────┘ └───────┘ └─────┘
Insert interval:          ┌─────────┐
                         | 2-7     |
After insert and merge: ┌───────────────┐
                        | 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 times.

An interval is like [start, 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]] is sorted because 6 > 3.

Result

You can quickly find where a new interval fits 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 or touch each other.

For example, [1,3] and [2,5] overlap because 2 and 3 are in both ranges. But [1,3] and [4,6] do not overlap because 4 is after 3.

Result

Knowing overlap helps decide when to merge intervals.

Recognizing overlap is key to keeping intervals non-overlapping after insertion.

3

Intermediate

Finding Insert Position in Sorted List

🤔Before reading on: do you think you should insert the new interval before, after, or between existing intervals? Commit to your answer.

Concept: The new interval should be inserted where its start time fits in the sorted order.

Scan the list from left to right. Insert the new interval before the first interval that starts after the new interval's start. If none, insert at the end.

Result

The list remains sorted by start times after insertion.

Knowing where to insert prevents breaking the sorted order and simplifies merging.

4

Intermediate

Merging Overlapping Intervals

🤔Before reading on: do you think merging means replacing intervals or just marking them? Commit to your answer.

Concept: Merge means combining overlapping intervals into one that covers all their ranges.

After insertion, check intervals before and after the new one. If they overlap, create a new interval with the smallest start and largest end among them. Remove the old intervals and insert the merged one.

Result

The list has no overlapping intervals and remains sorted.

Merging keeps the list clean and prevents confusion in range queries.

5

Intermediate

Handling Edge Cases in Merging

🤔Before reading on: do you think intervals that just touch (end equals start) should merge? Commit to your answer.

Concept: Intervals that touch (like [1,3] and [3,5]) are considered overlapping and should merge.

When checking overlap, use <= for start and end comparison, not just <. This ensures touching intervals merge into one continuous interval.

Result

No gaps remain between intervals that logically belong together.

Handling touching intervals avoids subtle bugs in interval management.

6

Advanced

Efficient Single-Pass Insert and Merge

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

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

Iterate through intervals: - Add all intervals ending before new interval starts. - Merge all overlapping intervals with new interval. - Add merged interval. - Add remaining intervals. This avoids multiple scans and extra memory.

Result

The final list is sorted, merged, and built efficiently in one pass.

One-pass approach improves performance and reduces complexity in real systems.

7

Expert

Handling Large Scale Interval Insertions

🤔Before reading on: do you think the same approach works well for millions of intervals? Commit to your answer.

Concept: For very large lists, naive scanning is slow; advanced data structures or batch processing help.

Use balanced trees or segment trees to store intervals for faster insertion and merging. Batch insertions can be sorted and merged offline before updating the main list. This reduces time from linear to logarithmic or better.

Result

Large-scale interval management becomes feasible and efficient.

Knowing limits of simple methods guides when to use advanced data structures in production.

Under the Hood

The algorithm scans the sorted list once, comparing each interval's start and end with the new interval. It collects intervals that do not overlap, merges overlapping ones by updating start and end boundaries, and constructs a new list. Internally, this uses simple comparisons and list operations, relying on the sorted property to avoid backtracking.

Why designed this way?

This approach minimizes complexity by leveraging the sorted order, avoiding nested loops or repeated scans. Historically, interval problems arise in scheduling and memory management, where efficiency and correctness are critical. Alternatives like interval trees exist but are more complex; this method balances simplicity and performance for common cases.

Input intervals: ┌─────┐ ┌───────┐ ┌─────┐
                 | 1-3 | | 6-9   | | 12-15|
                 └─────┘ └───────┘ └─────┘
New interval:          ┌─────────┐
                       | 2-7     |

Process flow:
[1-3] no overlap before new? Add to result.
[6-9] overlaps with new? Merge to [1-9].
[12-15] after merged? Add to result.

Output intervals: ┌───────────────┐ ┌─────┐
                  | 1-9           | |12-15|
                  └───────────────┘ └─────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think intervals that only touch at a point should be merged? Commit yes or no.

Common Belief: Intervals must overlap by at least one full unit to merge.

Reality: Intervals that touch at a boundary (end of one equals start of another) are merged to form a continuous interval.

Why it matters: Failing to merge touching intervals causes fragmented ranges and incorrect results in scheduling or range queries.

Quick: Do you think inserting an interval always increases the list size? Commit yes or no.

Common Belief: Inserting a new interval always adds one more interval to the list.

Reality: Insertion can reduce the number of intervals if the new interval merges multiple existing ones.

Why it matters: Assuming size always grows can lead to inefficient memory use or wrong assumptions about data structure size.

Quick: Do you think sorting the list after insertion is always necessary? Commit yes or no.

Common Belief: After inserting, you must sort the entire list again.

Reality: If the list is initially sorted and insertion is done correctly, the list remains sorted without extra sorting.

Why it matters: Unnecessary sorting wastes time and resources, especially for large lists.

Quick: Do you think merging intervals requires checking all pairs repeatedly? Commit yes or no.

Common Belief: Merging intervals requires comparing every pair multiple times.

Reality: Because the list is sorted, merging can be done in a single pass without repeated comparisons.

Why it matters: Misunderstanding this leads to inefficient algorithms and slower performance.

Expert Zone

1

Merging intervals that just touch (end equals start) is critical for correctness but often overlooked.

2

The one-pass insert-and-merge algorithm relies heavily on the input list being sorted; unsorted input breaks correctness.

3

In production, interval insertion often coexists with deletion and queries, requiring data structures like interval trees or segment trees.

When NOT to use

Avoid this simple insert-and-merge approach when intervals are unsorted or when frequent insertions and deletions happen dynamically; use interval trees or balanced search trees instead.

Production Patterns

Used in calendar apps to manage meeting times, in memory allocators to track free blocks, and in network systems to handle IP range allocations efficiently.

Connections

Interval Tree

Builds-on

Understanding insert and merge in sorted lists helps grasp how interval trees store and query overlapping intervals efficiently.

Merge Sort

Shares merging concept

The merging of intervals is similar to merging sorted lists in merge sort, reinforcing the power of sorted data for efficient combination.

Project Management Scheduling

Application domain

Knowing how intervals merge helps in scheduling tasks without conflicts, a key skill in project management.

Common Pitfalls

#1 Not merging intervals that only touch at boundaries.

Wrong approach:

if (interval.end < newInterval.start) { add interval; } else if (interval.start > newInterval.end) { add interval; } else { merge intervals; } // uses < and > only

Correct approach:

if (interval.end < newInterval.start) { add interval; } else if (interval.start > newInterval.end) { add interval; } else { merge intervals; } // use <= and >= for merging touching intervals

Root cause:

Misunderstanding that touching intervals are considered overlapping.

#2 Inserting new interval without considering sorted order.

Wrong approach:

intervals.push_back(newInterval); // just add at end without sorting or merging

Correct approach:

Find correct position by comparing starts, insert there, then merge overlapping intervals.

Root cause:

Ignoring the sorted property of the interval list.

#3 Sorting entire list after insertion unnecessarily.

Wrong approach:

intervals.push_back(newInterval); sort(intervals.begin(), intervals.end()); // sort whole list

Correct approach:

Insert at correct position and merge in one pass without full sort.

Root cause:

Not leveraging the existing sorted order.

Key Takeaways

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

Inserting a new interval requires placing it in sorted order and merging overlaps to keep the list clean.

Touching intervals are considered overlapping and must be merged to maintain continuous ranges.

A one-pass algorithm can efficiently insert and merge intervals without extra sorting.

For large or dynamic datasets, advanced data structures like interval trees are better suited than simple lists.

Practice

1. What is the main goal when inserting a new interval into a sorted list of non-overlapping intervals?

easy

A. To merge overlapping intervals and keep the list sorted

B. To add the new interval at the end without merging

C. To remove all intervals that come before the new interval

D. To sort the intervals again after insertion without merging

Solution

1. Step 1: Understand the problem context

   We have a sorted list of intervals that do not overlap. When inserting a new interval, we must keep the list sorted and merge any overlapping intervals.

2. Step 2: Identify the correct approach

   Simply adding the new interval without merging can cause overlaps. Sorting again without merging breaks the non-overlapping property. Removing intervals before the new one is incorrect.

3. Final Answer:

   To merge overlapping intervals and keep the list sorted -> Option A

4. Quick Check:

   Insert Interval = Merge and keep sorted [OK]

Hint: Always merge overlapping intervals after insertion [OK]

Common Mistakes:

• Inserting without merging overlaps
• Sorting intervals again without merging
• Removing intervals unnecessarily

2. Which of the following C++ code snippets correctly declares a vector of intervals where each interval is a pair of integers?

easy

A. std::vector intervals;

B. std::vector intervals;

C. std::vector intervals;

D. std::vector> intervals;

Solution

1. Step 1: Understand vector and pair syntax

   In C++, a vector of pairs is declared as std::vector>. The pair must specify both types inside angle brackets.

2. Step 2: Check each option

   std::vector> intervals; correctly uses std::pair. std::vector intervals; is invalid syntax for vector. std::vector intervals; misses the second type in pair. std::vector intervals; misses template parameters for pair.

3. Final Answer:

   std::vector> intervals; -> Option D

4. Quick Check:

   Vector of pairs syntax = std::vector> intervals; [OK]

Hint: Use std::vector> for intervals [OK]

Common Mistakes:

• Missing template parameters in pair
• Incorrect vector declaration syntax
• Using incomplete pair types

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, 3), (2, 5), (6, 9)]

B. [(1, 5), (6, 9)]

C. [(2, 5), (6, 9)]

D. [(1, 9)]

Solution

1. Step 1: Identify overlapping intervals

   The new interval (2, 5) overlaps with (1, 3) because 2 <= 3. They should be merged into (1, 5).

2. Step 2: Merge and keep other intervals

   After merging (1, 3) and (2, 5) into (1, 5), the interval (6, 9) remains unchanged.

3. Final Answer:

   [(1, 5), (6, 9)] -> Option B

4. Quick Check:

   Merge overlapping intervals = [(1, 5), (6, 9)] [OK]

Hint: Merge intervals if new start ≤ existing end [OK]

Common Mistakes:

• Not merging overlapping intervals
• Inserting without sorting
• Merging all intervals incorrectly

4. Consider the following C++ code snippet for inserting an interval into a sorted list of intervals:

std::vector> insertInterval(std::vector>& intervals, std::pair newInterval) {
    std::vector> result;
    int i = 0;
    while (i < intervals.size() && intervals[i].second < newInterval.first) {
        result.push_back(intervals[i]);
        i++;
    }
    while (i < intervals.size() && intervals[i].first <= newInterval.second) {
        newInterval.first = std::min(newInterval.first, intervals[i].first);
        newInterval.second = std::max(newInterval.second, intervals[i].second);
        i++;
    }
    result.push_back(newInterval);
    while (i < intervals.size()) {
        result.push_back(intervals[i]);
        i++;
    }
    return result;
}

What is the bug in this code if any?

medium

A. No bug; the code correctly inserts and merges intervals

B. The first while loop condition should use <= instead of <

C. The second while loop should check intervals[i].second instead of intervals[i].first

D. The newInterval is not pushed back at the correct position

Solution

1. Step 1: Analyze the first while loop

   The first loop adds all intervals that end before the new interval starts, correctly skipping non-overlapping intervals before newInterval.

2. Step 2: Analyze the second while loop

   The second loop merges all intervals overlapping with newInterval by updating its start and end correctly.

3. Step 3: Analyze the final steps

   After merging, newInterval is added, then remaining intervals are appended. This maintains sorted order and merges properly.

4. Final Answer:

   No bug; the code correctly inserts and merges intervals -> Option A

5. Quick Check:

   Code logic matches insert and merge steps [OK]

Hint: Check loop conditions carefully for overlap and order [OK]

Common Mistakes:

• Changing loop conditions incorrectly
• Pushing newInterval too early or late
• Merging intervals incorrectly

5. You have a sorted list of intervals: [(1, 2), (3, 5), (6, 7), (8, 10), (12, 16)]. You want to insert a new interval (4, 8). What is the final list after insertion and merging?

hard

A. [(1, 2), (3, 5), (4, 8), (6, 7), (8, 10), (12, 16)]

B. [(1, 2), (4, 10), (12, 16)]

C. [(1, 2), (3, 10), (12, 16)]

D. [(1, 2), (3, 8), (12, 16)]

Solution

1. Step 1: Identify intervals overlapping with (4, 8)

   Intervals (3, 5), (6, 7), and (8, 10) overlap with (4, 8) because their ranges intersect.

2. Step 2: Merge all overlapping intervals

   Merge (3, 5), (6, 7), (8, 10), and (4, 8) into one interval. The merged interval starts at min(3,4,6,8) = 3 and ends at max(5,7,8,10) = 10.

3. Step 3: Keep non-overlapping intervals

   Intervals (1, 2) and (12, 16) remain unchanged.

4. Final Answer:

   [(1, 2), (3, 10), (12, 16)] -> Option C

5. Quick Check:

   Merge overlapping intervals = [(1, 2), (3, 10), (12, 16)] [OK]

Hint: Merge all intervals overlapping new interval into one [OK]

Common Mistakes:

• Not merging all overlapping intervals
• Inserting new interval without merging
• Incorrect interval boundaries after merge