Question

How to merge all overlapping intervals in a given 2D array of intervals with C++

Answer 1

#include <iostream>
#include <vector>
#include <algorithm> // std::sort

using Interval = std::vector<int>;

std::vector<Interval> mergeIntervals(std::vector<Interval>& intervals) {
    if (intervals.empty()) return {};

    // Sort by start time
    std::sort(intervals.begin(), intervals.end(),
              [](const Interval& a, const Interval& b) {
                  return a[0] < b[0];
              });

    std::vector<Interval> merged;
    merged.push_back(intervals[0]);

    for (const auto& interval : intervals) {
        auto& last = merged.back();

        if (interval[0] <= last[1]) {
            // Overlap → extend the end
            last[1] = std::max(last[1], interval[1]);
        } else {
            // No overlap → new interval
            merged.push_back(interval);
        }
    }

    return merged;
}

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

    auto merged = mergeIntervals(intervals);

    std::cout << "Merged intervals:\n";
    for (const auto& iv : merged) {
        std::cout << "[" << iv[0] << ", " << iv[1] << "]\n";
    }
}



/*
run:

Merged intervals:
[1, 6]
[8, 10]
[15, 18]

*/

 

70+ SQL courses for beginners and professionals