Merge Intervals

Given a collection of intervals, represented as pairs of integers [start, end], where start denotes the start time of the interval and end denotes the end time of the interval. Merge overlapping intervals to create non-overlapping intervals.

Example:

Input:

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

Output:

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

Explanation: In the input, the intervals [1, 3] and [2, 6] overlap, so they can be merged into [1, 6]. The remaining intervals [8, 10] and [15, 18] are already non-overlapping. Thus, the merged intervals are [[1, 6], [8, 10], [15, 18]].

Merge Intervals Solution in C++:

#include <iostream>
#include <vector>
#include <algorithm>

// Function to merge overlapping intervals
std::vector<std::vector<int>> mergeIntervals(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) return {};

    // Sort the intervals based on their start time in ascending order
    std::sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
        return a[0] < b[0];
    });

    std::vector<std::vector<int>> mergedIntervals;
    mergedIntervals.push_back(intervals[0]);

    // Iterate through the sorted intervals
    for (int i = 1; i < intervals.size(); ++i) {
        int currStart = intervals[i][0];
        int currEnd = intervals[i][1];

        // If the current interval overlaps with the last merged interval, merge them
        if (currStart <= mergedIntervals.back()[1]) {
            mergedIntervals.back()[1] = std::max(mergedIntervals.back()[1], currEnd);
        } else {
            // If the current interval does not overlap, add it to the merged intervals
            mergedIntervals.push_back({currStart, currEnd});
        }
    }

    return mergedIntervals;
}

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

    std::vector<std::vector<int>> result = mergeIntervals(intervals);

    std::cout << "Merged Intervals:\n";
    for (const auto& interval : result) {
        std::cout << "[" << interval[0] << ", " << interval[1] << "] ";
    }
    std::cout << std::endl;

    return 0;
}

Merge Intervals Explanation:

1. The mergeIntervals function takes a reference to a vector of vectors intervals.
2. We first handle the edge case where the intervals vector is empty. If it’s empty, there are no intervals to merge, so we return an empty vector.
3. We sort the intervals vector based on their start time in ascending order using a custom comparator. This helps us find overlapping intervals efficiently.
4. We create a new vector mergedIntervals to store the merged intervals. We initialize it with the first interval from the sorted intervals vector.
5. We iterate through the sorted intervals starting from the second interval. For each interval, we compare its start time currStart with the end time of the last interval in mergedIntervals, denoted as mergedIntervals.back()[1]. If currStart is less than or equal to the end time of the last interval, it means the current interval overlaps with the last merged interval. In this case, we update the end time of the last merged interval to be the maximum of the current end time currEnd and the existing end time. This effectively merges the two overlapping intervals.
6. If the current interval does not overlap with the last merged interval, we add it to the mergedIntervals.
7. After processing all intervals, the mergedIntervals vector will contain non-overlapping intervals.

Time Complexity:

The time complexity of this solution is O(n log n), where n is the number of intervals in the input vector intervals. The main factor in the time complexity is the sorting step, which takes O(n log n) time using std::sort.

Space Complexity:

The space complexity of this solution is O(n), where n is the number of intervals in the input vector intervals. This is because we create a new vector mergedIntervals to store the merged intervals, and in the worst case, it can contain n intervals if all intervals are non-overlapping.