In cases like this, I'd suggest using a vector or deque ordered by end time (this optimizes for 'scheduling' a many intervals as possible), and simply iterate the list, skipping overlapping items:
#include <string>
#include <deque>
#include <algorithm>
using Timepoint = unsigned; // std::chrono::system_clock::time_point;
struct Entry {
Timepoint start, end;
std::string data;
};
#include <iostream>
int main()
{
std::deque<Entry> schedule {
{ 77472, 77504, "A" },
{ 77301, 77371, "B" },
{ 77406, 77439, "C" },
{ 77270, 77303, "D" },
{ 77302, 77570, "E" },
};
// order by end time_point
std::sort(begin(schedule), end(schedule), [](Entry const& a, Entry const& b) { return a.end < b.end; });
// now, iterate the schedule entries, skipping overlapping items
for(auto it = begin(schedule); it != end(schedule); )
{
auto const& entry = *it;
std::cout << "entry: " << entry.data << " from " << entry.start << " to " << entry.end << "\n";
// find next entry that doesn't overlap:
while (++it != end(schedule))
if (it->start > entry.end)
break;
}
}
There's probably a name for this algorithm: It's basically a scheduling algorithm that optimizes the number of jobs (as opposed to, e.g. total 'occupied' intervals) by always scheduling the next entry that would finish soonest.
The above code prints: (Live on Coliru):
entry: D from 77270 to 77303
entry: C from 77406 to 77439
entry: A from 77472 to 77504