Merge Overlapping Intervals in DSA C++ - Build from Scratch

Merge Overlapping Intervals

📖 Scenario: You are working on a calendar app that needs to combine overlapping meeting times into one continuous time slot. This helps users see their free time clearly.

🎯 Goal: Build a program that merges overlapping intervals from a list of meeting times and prints the merged intervals.

📋 What You'll Learn

Create a vector of pairs called intervals with given intervals

Create a variable merged to store merged intervals

Sort the intervals vector by start time

Use a for loop to merge overlapping intervals

Print the merged intervals in the format [start, end]

💡 Why This Matters

🌍 Real World

Merging intervals is useful in calendar apps, booking systems, and resource scheduling to avoid conflicts and show free time.

💼 Career

Understanding interval merging is important for software engineers working on scheduling, data processing, and optimization problems.

1

Create the initial intervals vector

Create a std::vector> called intervals with these exact intervals: {1, 3}, {2, 6}, {8, 10}, {15, 18}.

DSA C++

#include 
#include 
#include 

int main() {
    // Create the intervals vector here

    return 0;
}

Hint

Use std::vector with std::pair<int, int> and initialize with the given intervals.

2

Add a vector to store merged intervals

Add a std::vector> called merged to store the merged intervals.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    // Create merged vector here

    return 0;
}

Hint

Declare an empty vector called merged to hold the merged intervals.

3

Sort and merge the intervals

Sort the intervals vector by start time using std::sort. Then use a for loop with variable interval to iterate over intervals. Inside the loop, merge overlapping intervals by comparing with the last interval in merged and update or add intervals accordingly.

DSA C++

#include 
#include 
#include 
#include 

int main() {
    std::vector> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    std::vector> merged;

    // Sort intervals and merge overlapping intervals here

    return 0;
}

Hint

Sort intervals first. Then for each interval, if merged is empty or no overlap, add it. Otherwise, update the end of last merged interval.

4

Print the merged intervals

Use a for loop with variable interval to iterate over merged and print each interval in the format [start, end] separated by spaces.

DSA C++

#include 
#include 
#include 
#include 

int main() {
    std::vector> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    std::vector> merged;

    std::sort(intervals.begin(), intervals.end());

    for (const auto& interval : intervals) {
        if (merged.empty() || merged.back().second < interval.first) {
            merged.push_back(interval);
        } else {
            merged.back().second = std::max(merged.back().second, interval.second);
        }
    }

    // Print each merged interval in format [start, end] separated by spaces
    // Your code here

    return 0;
}

Hint

Loop over merged and print each interval with brackets and comma, separated by spaces.

Practice

1. What is the main purpose of the Merge Overlapping Intervals algorithm?

easy

A. To find the maximum interval length

B. To combine all intervals that overlap into a single continuous interval

C. To sort intervals in descending order

D. To remove all intervals that overlap

Solution

1. Step 1: Understand the problem goal

   The algorithm aims to merge intervals that share common parts so they become one continuous interval.

2. Step 2: Clarify what merging means

   Merging means combining overlapping intervals into one that covers the entire range of those intervals.

3. Final Answer:

   To combine all intervals that overlap into a single continuous interval -> Option B

4. Quick Check:

   Merge overlapping intervals = combine overlaps [OK]

Hint: Think of joining overlapping time slots into one [OK]

Common Mistakes:

• Confusing merging with sorting
• Thinking it removes intervals instead of combining
• Assuming it finds max length only

2. Which of the following C++ code snippets correctly sorts a vector of intervals by their start time before merging?

easy

A. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[0] < b[0]; });

B. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[1] > b[1]; });

C. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[1] < b[1]; });

D. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[0] > b[0]; });

Solution

1. Step 1: Identify sorting by start time

   We need to sort intervals by their first element (start time) in ascending order.

2. Step 2: Check lambda comparator correctness

   std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[0] < b[0]; }); uses a lambda that compares a[0] < b[0], which sorts ascending by start time correctly.

3. Final Answer:

   std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[0] < b[0]; }); -> Option A

4. Quick Check:

   Sort by start ascending = a[0] < b[0] [OK]

Hint: Sort intervals by start ascending using a lambda [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Sorting in descending order
• Using default sort without comparator on vector of vectors

3. What is the output of the following C++ code that merges overlapping intervals?

std::vector intervals = {{1,3},{2,6},{8,10},{15,18}};
// After merging overlapping intervals
// Print merged intervals
for (auto &interval : merged) {
    std::cout << "[" << interval[0] << "," << interval[1] << "] ";
}

medium

A. [1,6] [8,10] [15,18]

B. [1,3] [2,6] [8,10] [15,18]

C. [1,6] [2,6] [8,10] [15,18]

D. [1,3] [8,10] [15,18]

Solution

1. Step 1: Sort intervals by start time

   Sorted intervals: [1,3], [2,6], [8,10], [15,18]

2. Step 2: Merge overlapping intervals

   [1,3] and [2,6] overlap, merge to [1,6]. Others remain separate.

3. Final Answer:

   [1,6] [8,10] [15,18] -> Option A

4. Quick Check:

   Merged intervals = [1,6], [8,10], [15,18] [OK]

Hint: Merge intervals by expanding end if overlap found [OK]

Common Mistakes:

• Not merging overlapping intervals
• Printing original intervals without merge
• Merging incorrectly leaving duplicates

4. Identify the bug in this C++ code snippet for merging intervals:

std::vector mergeIntervals(std::vector &intervals) {
    std::vector merged;
    for (auto &interval : intervals) {
        if (merged.empty() || merged.back()[1] < interval[0]) {
            merged.push_back(interval);
        } else {
            merged.back()[1] = std::max(merged.back()[1], interval[1]);
        }
    }
    return merged;
}

medium

A. Pushing intervals without checking overlap

B. Using std::max incorrectly

C. Intervals are not sorted before merging

D. Returning merged by reference instead of value

Solution

1. Step 1: Check preconditions for merging

   Merging requires intervals sorted by start time to work correctly.

2. Step 2: Identify missing sorting step

   The code does not sort intervals before merging, so overlapping intervals may be missed.

3. Final Answer:

   Intervals are not sorted before merging -> Option C

4. Quick Check:

   Sort intervals first to merge correctly [OK]

Hint: Always sort intervals by start before merging [OK]

Common Mistakes:

• Skipping sorting step
• Assuming input is sorted
• Misusing std::max function

5. Given intervals [[1,4],[4,5],[7,9],[8,10]], what is the merged output after applying the merge overlapping intervals algorithm?

hard

A. [[1,10]]

B. [[1,4],[4,5],[7,9],[8,10]]

C. [[1,4],[5,7],[8,10]]

D. [[1,5],[7,10]]

Solution

1. Step 1: Sort intervals by start time

   Intervals are already sorted: [1,4], [4,5], [7,9], [8,10]

2. Step 2: Merge overlapping or touching intervals

   [1,4] and [4,5] touch at 4, merge to [1,5]. [7,9] and [8,10] overlap, merge to [7,10].

3. Final Answer:

   [[1,5],[7,10]] -> Option D

4. Quick Check:

   Touching intervals merge too [OK]

Hint: Merge intervals that overlap or touch at boundaries [OK]

Common Mistakes:

• Not merging intervals that touch at endpoints
• Leaving intervals separate when they overlap
• Merging all intervals incorrectly into one