Question

How to merge overlapping ranges (start,end),(start,end) in C++

Answer 1

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

std::vector<std::pair<int,int>> merge_ranges(std::vector<std::pair<int,int>> ranges) {
    // Sort by the first element of each pair
    std::sort(ranges.begin(), ranges.end(),
              [](const auto& a, const auto& b) {
                  return a.first < b.first;
              });

    std::vector<std::pair<int,int>> merged;

    for (const auto& r : ranges) {
        int start = r.first;
        int end   = r.second;

        if (merged.empty() || start > merged.back().second) {
            merged.emplace_back(start, end);
        } else {
            merged.back().second = std::max(merged.back().second, end);
        }
    }

    return merged;
}

int main() {
    std::vector<std::pair<int,int>> ranges = {
        {302, 447}, {488, 489}, {121, 234}, {200, 421}, {140, 354}
    };

    auto result = merge_ranges(ranges);

    for (const auto& r : result) {
        std::cout << "(" << r.first << ", " << r.second << ") ";
    }
}


/*
run:

(121, 447) (488, 489) 

*/

 

70+ SQL courses for beginners and professionals