Add things to an std::map by time range but interrogate by time value

Question

I am setting up an std::map object that links a series of time ranges (the key) to objects.

It is my intention to ensure that no two overlapping time range values can be added into this map - I know I can do this by creating a comparer function that returns true if there's an overlap and passing this in as the third comparer template item to the std::map.

However, I would like to look up the values based on a single point in time, not a range.

I think I need to override an operator but I'm not sure which - any ideas?

I need to be a bit quick as I think the office is about to close so apologies for any lack of detail/code.

Answer 1

You have three possible outcomes when you compare two ranges:

1. The first starts and ends before the second.
2. The first starts and ends after the second.
3. The two overlap.

You need to code your comparison function to reflect this relationship.

bool RangeLess(const range &r1, const range &r2)
{
    return r1.end < r2.start;
}

That was easy, wasn't it? If there's any overlap, both RangeLess(r1,r2) and RangeLess(r2,r1) will return false, and the two will be considered equivalent. An attempt to insert into a map will fail if there's already an equivalent item in the map.

To find a single time, use a range with the start and end values the same.

Answer 2

1. Add constructor that accepts a single value (time), and generates a range consisting of single point - beginning and end are same.

2. Override operator == for your range, so that it returns true if ranges overlap, false otherwise.

Now, you can lookup up key passing it a single value (time), whcih would default construct proper range, and return true if ranges overlap.

Answer 3

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