#include <algorithm>
#include <iostream>
#include <set>
#include <tuple>
#include <vector>

struct Interval
{
    double start;
    double end;
};

//-----------------------------------------------------------------------------
// Enum to qualify event: Start/End of "segment-line"
enum class EIntervalState
{
    Start,
    End
};

//-----------------------------------------------------------------------------
// Events used for collision detection
struct Event
{
    double pos;
    EIntervalState state;
    std::size_t id;
};

//-----------------------------------------------------------------------------
// Comparator to use if {1, 2} and {2, 3} should overlap
class LessIncludeLimit
{
public:
    bool operator()(const Event& lhs, const Event& rhs) const
    {
        return std::tie(lhs.pos, lhs.state) < std::tie(rhs.pos, rhs.state);
    }
};

//-----------------------------------------------------------------------------
// Comparator to use if {1, 2} and {2, 3} should not overlap
class LessExcludeLimit
{
public:
    bool operator()(const Event& lhs, const Event& rhs) const
    {
        return std::tie(lhs.pos, rhs.state) < std::tie(rhs.pos, lhs.state);
    }
};

//-----------------------------------------------------------------------------
std::vector<Event> MakeEvents(const std::vector<Interval>& intervals)
{
    std::vector<Event> res;
    std::size_t id = 0;
    for (const auto& interval : intervals)
    {
        res.push_back({interval.start, EIntervalState::Start, id});
        res.push_back({interval.end, EIntervalState::End, id});
        ++id;
    }
    return res;
}

//-----------------------------------------------------------------------------
template <typename Less>
std::vector<std::pair<std::size_t, std::size_t>>
ComputeOverlappingIntervals(std::vector<Event>&& events, Less less)
{
    std::sort(events.begin(), events.end(), less);

    std::set<std::size_t> activeIds;
    std::vector<std::pair<std::size_t, std::size_t>> res;

    for (const auto& event : events)
    {
        switch (event.state)
        {
            case EIntervalState::Start:
            {
                for (const auto& id : activeIds)
                {
                    res.emplace_back(std::minmax(event.id, id));
                }
                activeIds.emplace(event.id);
                break;
            }
            case EIntervalState::End:
            {
                activeIds.erase(event.id);
                break;
            }
        }
    }
    return res;
}

//-----------------------------------------------------------------------------
int main()
{
    const std::vector<Interval> intervals = {
        {1, 3},
                       {12, 14},
          {2, 4},
                          {13, 15},
                 {5, 10}
    };
    
    for (const auto& p : ComputeOverlappingIntervals(MakeEvents(intervals), LessExcludeLimit{})) {
       std::cout << "intervals " << p.first << " and " << p.second << " overlap\n";
    }
    
}