The “the interval covering problem” may have a nice mathematical intuition behind an alternative solution, with trivial data structures. Keep in mind that I am slightly noobish so I may be wrong (again), but hey nothing beats learning from mistakes 
Anyway: After sorting on left endpoints, starting from the left we can keep intersecting the intervals, the resulting intervals are non increasing and will eventually yield an empty intersection (If all tasks overlap at one common point then it wont be empty, but it is a corner case and it doesn’t change intuition). The last non empty interval is the smallest interval with elements that are common to all intersected intervals so far.
So the recipe goes like this:
- sort the intervals on left endpoint
- while there remain intervals{
-
select current interval -
while there remain intervals{ -
keep intersecting current with next interval, until intersection is empty, then take any endpoints (left or right) of the last non empty interval as a visit time}}
struct Interval
{
unsigned int left, right;
Interval(int l, int r) :left(l), right(r){}
bool operator<(const Interval &that){return this->left < that.left;}
};
bool Intersect(Interval &a, const Interval &b) {
if (min(a.right, b.right) < max(a.left, b.left))
return false; //empty intersection
a.left = max(a.left, b.left);
a.right= min(a.right, b.right);
return true;
}
vector Prob14_8(vector v) {
vector result;
sort(v.begin(), v.end());
int i = 0;
while (i != v.size()) {
Interval in = v[i];
while (i != v.size() && Intersect(in, v[i]))
++i;
result.push_back(in.left);
}
return result;
}
Let me know if you find some errors ! I have a simple test code if you want to try
void Prob14_8D() {
vector tasks;
tasks.push_back(Interval(0, 3)); tasks.push_back(Interval(2, 4));
tasks.push_back(Interval(3, 4)); tasks.push_back(Interval(1, 1));
tasks.push_back(Interval(5, 7)); tasks.push_back(Interval(7, 8));
tasks.push_back(Interval(8, 11)); tasks.push_back(Interval(9, 11));
tasks.push_back(Interval(12, 14)); tasks.push_back(Interval(12, 16));
tasks.push_back(Interval(13, 13)); tasks.push_back(Interval(16, 17));
vector results(Prob14_8(tasks));
for (const int &v : results)
cout << v << " ";
}