#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <iterator>

// исходные данные
typedef int Value;
typedef std::vector<Value> Source;

typedef std::vector<Source> Sources;
Sources sources;

// состояние вектора можно представить как диапазон итераторов
typedef Source::iterator SourceIter;
typedef std::pair<SourceIter,SourceIter> SourceRange;

SourceRange full_range(Source& s) { return SourceRange(s.begin(), s.end()); }
bool is_empty(SourceRange const& sr) { return sr.first == sr.second; }
Value peek(SourceRange const& sr) { return *sr.first; }
Value shift(SourceRange& sr) { return *sr.first++; }

std::ostream& operator<< (std::ostream& ost, SourceRange const& sr)
{
    ost << "[";
    std::copy(sr.first, sr.second, std::ostream_iterator<Value>(ost,","));
    ost << "]";
    return ost;
}

// очередь

struct Comparator // над непустыми диапазонами
{
    bool operator()(SourceRange const& l, SourceRange const& r) const
    {
        std::cout << "   -- comparing " << l << " to " << r << std::endl;
        return peek(l) > peek(r);
    }
};

typedef std::priority_queue<SourceRange, std::vector<SourceRange>, Comparator> Queue; // очередь из непустых диапазонов
Queue queue;

void add_to_queue(SourceRange const& sr)
{
    std::cout << " -- adding " << sr << std::endl;
    if(!is_empty(sr))
        queue.push(sr);
    std::cout << std::endl;
}

void add_to_queue_full_range(Source& s)
{
    add_to_queue(full_range(s));
}

// собственно, наша задача

void setup()
{
    for(Source& s : sources)
        add_to_queue_full_range(s);
}

bool done()
{
    return queue.empty();
}

Value next()
{
    SourceRange sr = queue.top();
    std::cout << " -- taking " << sr << std::endl;

    queue.pop();
    std::cout << std::endl;

    Value v = shift(sr);
    add_to_queue(sr);
    return v;
}

// проверяем

int main()
{
    sources = Sources {
        Source { 1, 5, 12, 28, 31 },
        Source { 6, 9, 13 },
        Source { 3, 7, 10, 15 },
    };

    setup();

    std::cout << "--------" << std::endl;
    while(!done())
    {
        Value v = next();
        std::cout << v << std::endl;
    }
}