Merge Overlapping Intervals In C++

Combining intersecting intervals is a prevalent computational issue found in diverse fields such as computer science, mathematics, and practical areas like scheduling, managing calendars, and analyzing data. The objective is to gather a set of intervals, with each interval denoting a specific value range, and combine any overlapping intervals into a unified and condensed interval. This procedure streamlines data representation and can assist in different activities like identifying open time frames, enhancing schedules, or streamlining data intricacies.

Interval Notation: An interval is commonly denoted as a pair of values [start, end], where start marks the commencement of the interval, and end indicates the conclusion. This notation denotes a closed interval, indicating that both the start and end points are encompassed within the interval.

Sorting is crucial for arranging intervals by their initial values to effectively combine overlapping intervals. This arrangement guarantees that intervals starting earliest are prioritized when identifying overlaps. Frequently employed sorting techniques include quicksort and mergesort algorithms.

Merging Process:

• ✅ Initialize an empty result set to store the merged intervals.
• ✅ Iterate through the sorted intervals one by one, starting from the first interval.
• ✅ For each interval, check if it overlaps with the previously merged interval (if any) by comparing its start value with the end value of the last merged interval.
• ✅ Suppose there is an overlap (i.e., start <= lastmergedend ), merge the current interval with the last merged interval. To do this, update the end value of the last merged interval to the maximum of its current end value and the end value of the current interval.
• ✅ If there is no overlap, add the current interval to the result set as a new merged interval.

After handling all intervals, the final set will encompass a series of non-overlapping intervals that span the identical range as the initial intervals, consolidating any overlapping intervals into a single merged interval.

This procedure streamlines the way intervals are depicted, simplifying data manipulation and analysis. It's crucial to understand that the effectiveness of this process relies heavily on the initial sorting phase, which commonly operates at a time complexity of O(n log n) for n intervals. Following sorting, the merging phase is straightforward, contributing to an overall time complexity of O(n log n) for the merging algorithm, primarily driven by the sorting procedure.

Program-1: Brute-Force Approach (Quadratic Time)

This method entails examining each interval against all other intervals to identify any overlaps. When encountering an overlap, merge the intersecting intervals. While this approach has a time complexity of O(n^2), it is relatively simple to execute.

#include <iostream>
#include <vector>
std::vector<std::pair<int, int>> mergeOverlappingIntervals(const std::vector<std::pair<int, int>>& intervals) {
    std::vector<std::pair<int, int>> mergedIntervals;
    for (const auto& current_interval : intervals) {
        bool merged = false;
        std::pair<int, int> merged_interval = current_interval;
        for (const auto& other_interval : intervals) {
            if (current_interval != other_interval) {
                if (current_interval.first <= other_interval.second && current_interval.second >= other_interval.first) {
                    // There is an overlap, merge the intervals.
                    merged_interval.first = std::min(current_interval.first, other_interval.first);
                    merged_interval.second = std::max(current_interval.second, other_interval.second);
                    merged = true;
                }
            }
        }
        if (!merged) {
            mergedIntervals.push_back(current_interval);
        } else {
            // Ensure the merged interval is not already in the result set.
            bool alreadyInResult = false;
            for (const auto& result_interval : mergedIntervals) {
                if (result_interval == merged_interval) {
                    alreadyInResult = true;
                    break;
                }
            }
            if (!alreadyInResult) {
                mergedIntervals.push_back(merged_interval);
            }
        }
    }
    return mergedIntervals;
}
int main() {
    std::vector<std::pair<int, int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    std::vector<std::pair<int, int>> merged = mergeOverlappingIntervals(intervals);
    for (const auto& interval : merged) {
        std::cout << "[" << interval.first << ", " << interval.second << "] ";
    }
    return 0;
}

Output:

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

Explanation:

Function Definition:

• ✅ The code defines a function named mergeOverlappingIntervals .
• ✅ It takes a vector of pairs of integers, representing intervals, as input.
• ✅ The function returns a vector of merged intervals.

Algorithm Overview:

• ✅ The function uses a brute-force approach to merge overlapping intervals.
• ✅ It iterates through each interval in the input vector and checks for overlaps with all other intervals.
• ✅ If an overlap is found, it merges the intervals.
• ✅ The merged intervals are stored in a new vector and returned.

Initialization:

A vector named mergedIntervals is established to contain the merged intervals.

Main Loop:

• ✅ This section of code sequentially processes each interval within the input vector.
• ✅ A nested loop is employed to evaluate the current interval against all other intervals.

Overlap Identification:

• ✅ This process involves verifying whether there exists an overlap between the present interval and another interval by comparing their start and end values.

Merging Overlapping Intervals:

In case of an overlap being identified, the script adjusts the existing interval to reflect the combined interval. The combined interval is defined with its beginning as the lower value between the starting points of the two intervals, and its conclusion as the higher value between the ending points of the two intervals.

Adding Combined Range to Output:

Upon comparing the present range with all other ranges, it gets included in the mergedRanges array.

To prevent redundancy, the script guarantees that combined ranges are not repeated in the final outcome.

• ✅ The function will provide the mergedIntervals vector which includes the merged intervals upon execution.

Complexity Analysis

Time Complexity:

• ✅ The main loop iterates through each interval in the input vector, resulting in O(n) iterations, where n is the number of intervals.
• ✅ For each interval in the main loop, there is a nested loop that iterates through all other intervals. In the worst case, this nested loop compares the current interval with every other interval, resulting in O(n) comparisons for each interval in the main loop.
• ✅ Therefore, the overall time complexity is O(n^2) , where n is the number of intervals.

Space Complexity:

• ✅ The space complexity is primarily determined by the storage of the merged intervals in the mergedIntervals vector.
• ✅ In the worst case, if no intervals can be merged, the mergedIntervals vector will contain the same number of intervals as the input vector, resulting in a space complexity of O(n) .
• ✅ Additionally, there are some auxiliary variables used for comparisons and temporary storage, but their space usage is relatively small and doesn't significantly impact the overall space complexity.

In essence, the given brute-force method exhibits a time complexity of O(n^2) and a space complexity of O(n), where n represents the quantity of intervals within the input array. This strategy is notably less effective when juxtaposed with sorting-based methodologies, capable of attaining a time complexity of O(n log n) alongside a space complexity of O(n).

Program-2: Sorting and Merging (Linear Arithmetic Time)

Step 1: Sorting the Intervals

• ✅ In this method, the first step is to sort the input intervals based on their start values.
• ✅ Sorting is essential because it helps group overlapping intervals together, making it easier to identify and merge them.
• ✅ Common sorting algorithms like quicksort or mergesort are typically used here, which have an average time complexity of O(n log n) .

After arranging the intervals in order, proceed with iterating through them sequentially. Keep a variable, commonly named mergedIntervals or a similar identifier, to hold the combined intervals.

Iterative Merging Process:

• ✅ Start with the first interval (the one with the smallest start value) and consider it as the "current interval" .
• ✅ Move to the next interval and check if it overlaps with the current interval.
• ✅ After that, compare the start of the current interval with the end of the next interval to determine overlap.
• ✅ If the start of the current interval is less than or equal to the end of the next interval, it means they overlap.
• ✅ If they overlap, merge the two intervals by updating the end of the current interval to be the maximum of its current end and the end of the next interval.
• ✅ If there's no overlap, add the current interval to the result ( mergedIntervals ) because you've found the end of this merged interval.
• ✅ Continue this process, moving through the sorted intervals one by one, merging overlapping intervals when encountered.

Example:

#include <iostream>
#include <vector>
#include <algorithm>
std::vector<std::pair<int, int>> mergeOverlappingIntervals(const std::vector<std::pair<int, int>>& intervals) {
    if (intervals.empty()) {
        return {};  // Return an empty vector if there are no intervals.
    }
    // Sort the intervals based on their start values.
    std::vector<std::pair<int, int>> sortedIntervals = intervals;
    std::sort(sortedIntervals.begin(), sortedIntervals.end());
    std::vector<std::pair<int, int>> mergedIntervals;
    mergedIntervals.push_back(sortedIntervals[0]);
    for (int i = 1; i < sortedIntervals.size(); ++i) {
        std::pair<int, int> currentInterval = sortedIntervals[i];
        std::pair<int, int>& lastMergedInterval = mergedIntervals.back();
        if (currentInterval.first <= lastMergedInterval.second) {
            // Merge the overlapping intervals.
            lastMergedInterval.second = std::max(lastMergedInterval.second, currentInterval.second);
        } else {
            // No overlap, add the current interval to the result.
            mergedIntervals.push_back(currentInterval);
        }
    }
    return mergedIntervals;
}
int main() {
    std::vector<std::pair<int, int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    std::vector<std::pair<int, int>> merged = mergeOverlappingIntervals(intervals);
    for (const auto& interval : merged) {
        std::cout << "[" << interval.first << ", " << interval.second << "] ";
    }
    return 0;
}

Output:

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

Explanation:

• ✅ In this example, a function named mergeOverlappingIntervals is defined, which takes a vector of intervals as input.
• ✅ The code checks if the input vector of intervals is empty. If it's empty, the function returns an empty vector, as there are no intervals to merge.
• ✅ The intervals are sorted based on their start values using the std::sort Sorting ensures that overlapping intervals are adjacent, simplifying the merging process.
• ✅ A new vector called mergedIntervals is created to store the merged intervals.
• ✅ The first interval (the one with the smallest start value) is added to mergedIntervals as the initial merged interval.
• ✅ After that, the code iterates through the sorted intervals starting from the second interval.
• ✅ It checks if there is an overlap with the last merged interval (the one at the end of the mergedIntervals vector).
• ✅ If there is an overlap, the code merges the current interval with the last merged interval by extending the end of the last merged interval if necessary.
• ✅ If there is no overlap, the current interval is added to the mergedIntervals vector as a new merged interval.
• ✅ The mergedIntervals vector now contains the merged intervals with no overlaps. These merged intervals represent the non-overlapping ranges obtained from the input intervals.
• ✅ The function returns the mergedIntervals vector as the result.

Complexity Analysis

Time Complexity :

• ✅ The time complexity of this approach is mainly determined by the sorting step, which has a time complexity of O(n log n) , where n is the number of intervals.
• ✅ The merging step, which follows, is linear in time complexity because it processes each interval once.
• ✅ Overall, the time complexity of this method is O(n log n) due to the sorting step, and it is considered efficient for handling large datasets.

Space Complexity:

• ✅ The space complexity primarily depends on the space required to store the sorted intervals and the merged intervals.
• ✅ Sorting is typically done in-place on the original intervals, so it doesn't significantly impact the space complexity.
• ✅ The merged intervals are stored in a separate vector or data structure, which has a space complexity of O(n) , as it may contain all intervals if there are no overlaps.

In brief, the technique of "Sorting and Merging" effectively combines intersecting intervals with a time complexity of O(n log n) attributable to the sorting process. It is well-suited for managing extensive data sets and is a commonly used strategy for addressing this issue in real-world scenarios.

Program-3:Stack-based Approach (Linear Time)

• ✅ Sort the intervals based on their start values .
• ✅ Initialize an empty stack to store merged intervals.
• ✅ Iterate through the sorted intervals, pushing intervals onto the stack if they don't overlap with the top interval, and merging them if they do.

Example:

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
std::vector<std::pair<int, int>> mergeOverlappingIntervals(const std::vector<std::pair<int, int>>& intervals) {
    // Check if the input intervals are empty.
    if (intervals.empty()) {
        return {};
    }
    // Sort the intervals based on their start values.
    std::vector<std::pair<int, int>> sortedIntervals = intervals;
    std::sort(sortedIntervals.begin(), sortedIntervals.end());
    // Create a stack to hold merged intervals.
    std::stack<std::pair<int, int>> intervalStack;
    intervalStack.push(sortedIntervals[0]);
    // Iterate through the sorted intervals and merge overlapping ones.
    for (int i = 1; i < sortedIntervals.size(); ++i) {
        std::pair<int, int> currentInterval = sortedIntervals[i];
        std::pair<int, int> topInterval = intervalStack.top();
        if (currentInterval.first <= topInterval.second) {
            // Overlapping intervals, merge them.
            intervalStack.pop();
            topInterval.second = std::max(topInterval.second, currentInterval.second);
            intervalStack.push(topInterval);
        } else {
            // Non-overlapping interval, push it onto the stack.
            intervalStack.push(currentInterval);
        }
    }
    // Extract merged intervals from the stack.
    std::vector<std::pair<int, int>> mergedIntervals;
    while (!intervalStack.empty()) {
        mergedIntervals.push_back(intervalStack.top());
        intervalStack.pop();
    }
    // Reverse the order to get intervals in the correct order.
    std::reverse(mergedIntervals.begin(), mergedIntervals.end());
    return mergedIntervals;
}
int main() {
    std::vector<std::pair<int, int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    std::vector<std::pair<int, int>> merged = mergeOverlappingIntervals(intervals);
    for (const auto& interval : merged) {
        std::cout << "[" << interval.first << ", " << interval.second << "] ";
    }
    return 0;
}

Output:

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

Explanation:

• ✅ A function named mergeOverlappingIntervals is defined to take a vector of intervals as input.
• ✅ The code checks if the input vector of intervals is empty. If it's empty, the function returns an empty vector, indicating that there are no intervals to merge.
• ✅ The intervals are sorted based on their start values using the std::sort Sorting ensures that overlapping intervals are adjacent, making it easier to merge them.
• ✅ A stack called intervalStack is created to hold intervals during the merging process.
• ✅ The code iterates through the sorted intervals starting from the second interval.
• ✅ It checks if there is an overlap with the interval at the top of the stack (the last merged interval).
• ✅ If there is an overlap, the code merges the current interval with the interval at the top of the stack by extending the end of the last merged interval if necessary.
• ✅ If there is no overlap, the current interval is pushed onto the stack as a new interval to be merged.
• ✅ After processing all intervals, the merged intervals are extracted from the stack and stored in a vector called mergedIntervals.
• ✅ The code reverses the order of intervals in the mergedIntervals vector to obtain the merged intervals in the correct order (from left to right).
• ✅ The function returns the mergedIntervals vector, which now contains the merged non-overlapping intervals.

In essence, this method based on stacks effectively combines intersecting intervals by cycling through the arranged intervals and employing a stack to handle the merging operation. The outcome is an array of merged intervals devoid of any overlaps.

Complexity Analysis

Time Complexity:

• ✅ Sorting the intervals initially takes O(n log n) time, where 'n' is the number of intervals.
• ✅ The subsequent iteration through the sorted intervals is linear, i.e., O(n) .
• ✅ Each interval is pushed onto or popped from the stack exactly once, which is also O(n) .
• ✅ Overall, the time complexity is dominated by the sorting step, resulting in a time complexity of O(n log n) .

Space Complexity:

The space complexity primarily depends on the usage of additional data structures:

• ✅ A sorted copy of the intervals is created, which requires O(n) additional space.
• ✅ A stack is used to hold intervals during merging, which may temporarily store up to O(n) intervals in the worst cases.
• ✅ The mergedIntervals vector stores the merged intervals, which can also have a maximum size of O(n) .
• ✅ Therefore, the space complexity is O(n) due to the additional data structures.
• ✅ The stack-based approach for merging overlapping intervals has a time complexity of O(n log n) and a space complexity of O(n) , making it an efficient method for handling large datasets of intervals.

Program-4: Binary Search Tree Approach

An alternative method for combining intersecting intervals in C++ involves employing a Binary Search Tree (BST) data structure. The following is a broad overview of this strategy:

Define a Framework for Interval Nodes: Develop a blueprint to depict interval nodes, housing the initial and concluding values of an interval along with pointers to the BST's left and right offspring nodes.

Inserting Intervals into the Binary Search Tree (BST): Each interval is inserted into the BST according to its starting value. While inserting, it's crucial to address scenarios where the new interval might intersect with current nodes. In such instances, adjust the end value of the intersecting interval node to the greater value between the new interval's end and the existing node's end.

Traversing the Binary Search Tree (BST): Performing an in-order traversal of the BST enables you to obtain the intervals in a sorted manner. During the traversal process, you have the opportunity to combine intervals, adjusting them whenever there are overlaps that occur.

When performing an in-order traversal, it is possible to manage a stack to monitor the merged intervals. By examining each interval node, you can check for overlaps with the topmost interval in the stack. In case of an overlap, combine the intervals; if not, add the current interval to the stack.

Example:

#include <iostream>
#include <vector>
#include <stack>
struct Interval {
    int start;
    int end;
    Interval(int s, int e) : start(s), end(e) {}
};
struct IntervalNode {
    Interval interval;
    IntervalNode* left;
    IntervalNode* right;
    IntervalNode(const Interval& i) : interval(i), left(nullptr), right(nullptr) {}
};
void insertInterval(IntervalNode*& root, const Interval& newInterval) {
    if (!root) {
        root = new IntervalNode(newInterval);
        return;
    }
    if (newInterval.end < root->interval.start) {
        insertInterval(root->left, newInterval);
    } else if (newInterval.start > root->interval.end) {
        insertInterval(root->right, newInterval);
    } else {
        // Merge overlapping intervals
        root->interval.start = std::min(root->interval.start, newInterval.start);
        root->interval.end = std::max(root->interval.end, newInterval.end);
    }
}
void inOrderTraversal(IntervalNode* root, std::vector<Interval>& mergedIntervals) {
    if (!root) {
        return;
    }
    inOrderTraversal(root->left, mergedIntervals);
    mergedIntervals.push_back(root->interval);
    inOrderTraversal(root->right, mergedIntervals);
}
std::vector<Interval> mergeOverlappingIntervals(const std::vector<Interval>& intervals) {
    IntervalNode* root = nullptr;
    for (const Interval& interval : intervals) {
        insertInterval(root, interval);
    }
    std::vector<Interval> mergedIntervals;
    inOrderTraversal(root, mergedIntervals);
    return mergedIntervals;
}
int main() {
    std::vector<Interval> intervals = {Interval(1, 3), Interval(2, 6), Interval(8, 10), Interval(15, 18)};
    std::vector<Interval> merged = mergeOverlappingIntervals(intervals);
    for (const Interval& interval : merged) {
        std::cout << "[" << interval.start << ", " << interval.end << "] ";
    }
    return 0;
}

Output:

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

Explanation:

In this instance, the code starts by importing essential C++ libraries for managing input/output operations (iostream), manipulating arrays (vector), and using data structures like stacks (stack).

It defines two custom data structures:

Interval: Represents a range defined by a beginning and ending point.

IntervalNode: Describes a node within a Binary Search Tree (BST) that contains an interval, along with both left and right child nodes.

The process of adding intervals into the BST is managed by the insertInterval function, which guarantees the merging of overlapping intervals. Should a new interval overlap with one already existing in the tree, it adjusts the boundaries of the existing interval to envelop both intervals.

For the collection of merged intervals, the inOrderTraversal function executes an in-order traversal of the BST. This traversal is crucial for gathering intervals in a sorted manner, appending them to the mergedIntervals vector.

The main function, mergeOverlappingIntervals , orchestrates the entire process:

• ✅ It initializes an empty BST (root).
• ✅ Iterates through the input intervals, inserting them into the BST.
• ✅ Calls the inOrderTraversal function to populate the mergedIntervals vector with merged intervals.
• ✅ The merged intervals are returned as a vector from the mergeOverlappingIntervals
• ✅ In the main function, sample intervals are provided, and the code prints the merged intervals to the console.
• ✅ The program concludes by returning 0 to indicate successful execution.
• ✅ This approach uses a Binary Search Tree to efficiently merge overlapping intervals, resulting in a vector of non-overlapping intervals. The core idea is to maintain intervals in sorted order using the BST, which simplifies the merging process and produces the desired merged intervals.

Complexity Analysis:

Time Complexity:

• ✅ The time complexity for inserting 'n' intervals into a BST can vary but is typically O(n log n) for a well-balanced tree. In the worst case, when the tree becomes degenerate (linear), it can be O(n^2) . However, on average, it tends to be O(n log n) with a well-balanced tree.
• ✅ The in-order traversal of a BST takes O(n) time since it processes each node once.
• ✅ Overall, the time complexity of the code is mainly dominated by the BST insertion step, which is O(n * log n) on average for a balanced tree.

Space Complexity:

• ✅ The space complexity for storing the intervals in the BST is O(n) because, in the worst case, the BST may contain 'n' nodes (one for each interval).
• ✅ The mergedIntervals vector stores the merged intervals, which can also have a maximum size of 'n' .
• ✅ The code uses a small amount of additional space for variables and function call stacks, but these do not significantly impact the overall space complexity.
• ✅ The overall space complexity of the code is O(n) due to the storage of intervals in the BST and the mergedIntervals vector.

Benefits of Merging Overlapping Intervals:

There are numerous advantages of utilizing the Merging Overlapping Intervals technique. Some key benefits of employing the Merging Overlapping Intervals include:

Consolidating overlapping intervals is a technique used to decrease the volume of data to handle. This method is especially beneficial in situations involving extensive sets of intervals, like scheduling, where the combined intervals signify unified time segments. This optimization helps conserve memory and computational capabilities.

Enhanced Representation: Consolidating intervals enhances data visualization by condensing multiple individual intervals into a reduced set of merged intervals. This streamlines data interpretation and facilitates clearer presentation in visual aids such as graphs or charts.

Merged intervals streamline data analysis processes by allowing focus on overarching time frames instead of individual events or intervals. This consolidation promotes more effective and uncomplicated analysis.

Drawbacks of Merging Overlapping Intervals:

There are numerous limitations associated with the process of Merging Overlapping Intervals. Some key disadvantages of this technique include:

Combining intervals can result in a decrease in accuracy. When intervals are merged, detailed timing information or events happening within those merged intervals may no longer be available. This could pose a challenge in scenarios where exact timing is crucial.

Implementing interval merging algorithms can be intricate, particularly when handling numerous intervals or when there are additional constraints to take into account. The procedure of sorting and merging can lead to increased computational overhead.

Application-Specific: The advantages and constraints of combining intervals vary depending on the application. What may be successful in one scenario could be less efficient in another. It is essential to grasp the particular needs of your problem to select the most suitable method.