#include <set>
#include <vector>
#include <algorithm>
#define DBG(x)
//
// Heap-based solution
// Given data of the form (ID, Next ID, Time), compute
// some basic stuff about it...
// Make the assumption that the IDs always go up from the previous ID.
// They do in the example, but there is no reason we should assume that
// in general.
//
struct HeapEntry
{
int m_start;
int m_end;
int m_total_time;
int m_item_count;
HeapEntry( int st, int en, int ti )
: m_start(st), m_end(en), m_total_time(ti), m_item_count(1)
{}
HeapEntry( const HeapEntry& h )
: m_start(h.m_start), m_end(h.m_end)
, m_total_time(h.m_total_time), m_item_count(h.m_item_count)
{}
void update( int new_end, int t )
{
m_total_time += t;
m_end = new_end;
m_item_count++;
}
void update( int t )
{
m_total_time += t;
m_item_count++;
}
};
struct DoneCompare
{
bool operator()( const HeapEntry& h1, const HeapEntry& h2 ) const
{
return (h1.m_total_time < h2.m_total_time) |
( (h1.m_total_time == h2.m_total_time) & (h1.m_item_count < h2.m_item_count) );
}
};
struct HeapCompare
{
bool operator()( const HeapEntry& h1, const HeapEntry& h2 ) const
{
return h1.m_end > h2.m_end;
}
};
class HeapSolution
{
private:
int m_last = 0;
std::vector< HeapEntry > m_heap;
std::multiset< HeapEntry, DoneCompare > m_done_set;
HeapCompare m_heap_compare;
public:
HeapSolution()
{
m_heap.push_back( HeapEntry(INT_MAX, INT_MAX, INT_MAX) );
}
~HeapSolution() = default;
void insert( int start, int end, int time )
{
// Assumption : All IDs go forward. Enforce it.
if (start <= m_last)
{
throw std::string("Error : job IDs going backwards.");
}
m_last = start;
DBG(
std::cout << "Insert : m_heap[0].end " << m_heap[0].m_end << ", start " << start << "\n";
)
// Next element in THIS list...
if (m_heap[0].m_end == start)
{
if (end == 0)
{
m_heap[0].update(time);
std::pop_heap( m_heap.begin(), m_heap.end(), m_heap_compare);
m_done_set.insert( m_heap.back() );
m_heap.pop_back();
}
else
{
std::pop_heap( m_heap.begin(), m_heap.end(), m_heap_compare );
m_heap.back().update( end, time );
std::push_heap( m_heap.begin(), m_heap.end(), m_heap_compare );
}
}
else if ( end == 0 )
{
// Insert a new element : list only has 1 element. Done!
m_done_set.insert( HeapEntry( start, start, time ) );
}
else
{
// Insert a new element into the list
m_heap.push_back( HeapEntry(start,end,time) );
std::push_heap( m_heap.begin(), m_heap.end(), m_heap_compare );
}
DBG(
std::cout << "Bottom of insert : ";
for (const auto& s : m_heap )
{
std::cout << " (" << s.m_end << "," << s.m_start << "," << s.m_item_count
<< "," << s.m_total_time << ")";
}
std::cout << "\n";
);
}
std::ostream& output( std::ostream& ostr )
{
int count = 0;
// Verify we've emptied the map...
if (m_heap.size() != 1)
{
std::cout << "Note : List is not empty.\n";
}
// Walk the map.
for ( auto &entry : m_done_set)
{
// Total Time to finish all jobs
// Total # of jobs
// Average Time per Job
ostr << "List : " << (++count) << " :\n"
<< "\tStart " << entry.m_start << ", End " << entry.m_end << "\n"
<< "\tTotal Time : "
<< entry.m_total_time
<< ". Number of Jobs : " << entry.m_item_count
<< ". Average time per job : "
<< (entry.m_total_time / (double) entry.m_item_count)
<< "\n";
}
return ostr;
}
};
