Merge Intervals
(algo/sequence/merge_intervals.hpp)

• View this file on GitHub
• Last update: 2026-08-21 12:49:11+09:00
• Include: #include "algo/sequence/merge_intervals.hpp"

Overview

Computes the union of half-open intervals. The result is sorted by left endpoint, contains no empty intervals, and has a positive gap between every two consecutive intervals. In particular, overlapping or touching intervals are merged.

Every input interval must satisfy left <= right. Endpoints must be movable and support a strict weak ordering through operator<; passing an lvalue vector also requires them to be copyable.

Functions

Function	Description	Complexity
vector<pair<T, T>> merge_intervals(vector<pair<T, T>> intervals)	Returns the union of the half-open intervals [left, right). The argument is copied when an lvalue is passed and can be consumed with std::move.	$O(N \log N)$ time and $O(1)$ auxiliary space

Notes

• Empty intervals [x, x) are discarded.
• Touching intervals such as [1, 3) and [3, 5) become [1, 5).
• A reversed interval violates the function precondition and triggers an assertion in debug builds.
• The input vector is not modified unless the caller explicitly passes it with std::move.

Example

#include "algo/sequence/merge_intervals.hpp"

#include <utility>
#include <vector>

int main() {
    std::vector<std::pair<int, int>> intervals;
    intervals.emplace_back(5, 8);
    intervals.emplace_back(1, 3);
    intervals.emplace_back(3, 6);
    intervals.emplace_back(9, 9);

    auto merged = m1une::algo::merge_intervals(intervals);
    // merged contains [1, 8).
}

Required by

• Algorithms All (algo/all.hpp)
• Sequence Algorithms All (algo/sequence/all.hpp)

Verified with

• verify/algo/sequence/merge_intervals.test.cpp

Code

#ifndef M1UNE_ALGO_SEQUENCE_MERGE_INTERVALS_HPP
#define M1UNE_ALGO_SEQUENCE_MERGE_INTERVALS_HPP 1

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

namespace m1une {
namespace algo {

// Returns the union of half-open intervals as sorted, disjoint intervals.
template <typename T>
std::vector<std::pair<T, T>> merge_intervals(
    std::vector<std::pair<T, T>> intervals
) {
    for (const auto& [left, right] : intervals) {
        if (right < left) assert(false);
    }

    std::sort(
        intervals.begin(),
        intervals.end(),
        [](const auto& lhs, const auto& rhs) {
            if (lhs.first < rhs.first) return true;
            if (rhs.first < lhs.first) return false;
            return lhs.second < rhs.second;
        }
    );

    std::size_t result_size = 0;
    for (std::size_t index = 0; index < intervals.size(); ++index) {
        auto& [left, right] = intervals[index];
        if (!(left < right)) continue;
        if (result_size == 0 || intervals[result_size - 1].second < left) {
            if (result_size != index) {
                intervals[result_size] = std::move(intervals[index]);
            }
            ++result_size;
        } else if (intervals[result_size - 1].second < right) {
            intervals[result_size - 1].second = std::move(right);
        }
    }
    intervals.erase(intervals.begin() + result_size, intervals.end());
    return intervals;
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_SEQUENCE_MERGE_INTERVALS_HPP

#line 1 "algo/sequence/merge_intervals.hpp"



#include <algorithm>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

namespace m1une {
namespace algo {

// Returns the union of half-open intervals as sorted, disjoint intervals.
template <typename T>
std::vector<std::pair<T, T>> merge_intervals(
    std::vector<std::pair<T, T>> intervals
) {
    for (const auto& [left, right] : intervals) {
        if (right < left) assert(false);
    }

    std::sort(
        intervals.begin(),
        intervals.end(),
        [](const auto& lhs, const auto& rhs) {
            if (lhs.first < rhs.first) return true;
            if (rhs.first < lhs.first) return false;
            return lhs.second < rhs.second;
        }
    );

    std::size_t result_size = 0;
    for (std::size_t index = 0; index < intervals.size(); ++index) {
        auto& [left, right] = intervals[index];
        if (!(left < right)) continue;
        if (result_size == 0 || intervals[result_size - 1].second < left) {
            if (result_size != index) {
                intervals[result_size] = std::move(intervals[index]);
            }
            ++result_size;
        } else if (intervals[result_size - 1].second < right) {
            intervals[result_size - 1].second = std::move(right);
        }
    }
    intervals.erase(intervals.begin() + result_size, intervals.end());
    return intervals;
}

}  // namespace algo
}  // namespace m1une

Back to top page