Finding closest 20 minute interval from current time

I have an array of dates and times like so:

[["2023-Aug-08", "00:00", "302.218616", "-21.391909"],
["2023-Aug-08", "00:20", "306.564766", "-24.382470"],
["2023-Aug-08", "00:40", "311.149963", "-27.204929"]
...

Each index increments by 20 minutes and continues for 24 hours.

I want to find a way to sort through the times specifically so that I can find the closest interval to the current time (say its 2:34, I want the get the index that has 2:40 in it and if its 2:29 I am looking for 2:20).

I am using the time library to get the hours and minutes as a string but I'm not sure how I can use that to compare to the existing times.

In C++20 I would use <chrono>. Unfortunately implementations are still coming online. Your vendor may or may not have implemented it yet. Or there may be other reasons you can not yet use C++20. If this is the case you can use this free, open-source C++20 <chrono> preview library which will easily port to C++20 <chrono>.

The basic idea will be to use the std::chrono::round function to round to the nearest 20min interval. But the first job is to parse your data out of string form into a data structure you can efficiently compute with:

#include <chrono>
#include <iostream>
#include <map>
#include <sstream>

std::pair<std::chrono::sys_time<std::chrono::minutes>, double>
parse_data(char const* date, char const* time, char const* data)
{
    using namespace std;
    using namespace chrono;

    istringstream in{string{date} + ' ' + time + ' ' + data};
    in.exceptions(ios::failbit);
    sys_time<minutes> tp;
    double item;
    in >> parse("%Y-%b-%d %H:%M", tp) >> item;
    return {tp, item};
}

This parses everything into a pair<sys_time<minutes>, double>. double is just a stand-in for whatever data you have associated with the date. sys_time<minutes> is a minute-precision date-time that represents UTC. If this is some local time, you can trivially change the type of sys_time to local_time.

I've chosen to throw an exception if the parse fails. Other error checking is also possible.

With this helper function it is trivial to fill a std::map with your data:

int
main()
{
    using namespace std;
    using namespace chrono;

    char const* dates[][3] = {{"2023-Aug-08", "00:00", "1.0"},
                              {"2023-Aug-08", "00:20", "3.14"},
                              {"2023-Aug-08", "00:40", "2.71"}};

    map<sys_time<minutes>, double> m;
    for (auto const& i : dates)
        m.insert(parse_data(i[0], i[1], i[2]));
    ...

• Declare your map
• For each row of data, use your parsing function to insert a row into the map

Now you can easily look up items in the map. First declare a duration type of length 20min so that you can easily round to it:

using duodecamin = duration<minutes::rep,
                            ratio_multiply<ratio<20>, minutes::period>>;

Now given timepoints you can round to the nearest 20min interval and look that value up in the map:

auto now = sys_days{2023y/August/8} + 34min;
cout << m[round<duodecamin>(now)] << '\n';
     now = sys_days{2023y/August/8} + 29min;
cout << m[round<duodecamin>(now)] << '\n';

Output:

2.71
3.14

now could have just as easily come from:

auto now = system_clock::now();

First off, you want to parse each of those date-time sublists into a datetime object. There's plenty resources on how to do things like that out there;. here is a good start.

Once you have your 20 minute intervals turned into a list of datetime objects, we can have the search algorithm.

Here's an initial sketch for a naive approach. It makes a "distance" value from each item in the list, then uses index and min to get the index of the minimum value.

import datetime

def find_closest(datetimes, when):
    distances = [abs((dt - when).total_seconds()) for dt in datetimes]
    return datetimes[distances.index(min(distances))]

However, this is not a very good algorithm. You see, it has to compute the distance for every single item, and then do a linear search to figure out which is the smallest. This means iterating over the full list twice!

But with a sorted list, it is possible to get better performance on very large lists with a sort of binary search.

import datetime


def find_closest(datetimes: list[datetime.datetime], when: datetime.datetime):
    "Finds and returns the datetime in `datetimes` that is closest to `when`."
    datetimes = sorted(datetimes)

    low = 0
    high = len(datetimes) - 1

    while high - low > 1:
        center = (high + low) // 2
        here = datetimes[center]
        distance = abs((here - when).total_seconds())

        # Print below is to demonstrate the algorithm - feel free to comment out.
        print(
            f"High {high}, low {low}, center {center} - time at center is {here}, offset of {distance}"
        )

        if distance == 0:
            print("Exact match found")
            return here

        elif when > here:
            # when is later so look later on
            low = center

        else:
            high = center

    # No datetime is exactly equal to 'when'.
    dt_low = datetimes[low]
    dt_high = datetimes[low]

    if abs((dt_low - when).total_seconds()) < abs((dt_high - when).total_seconds()):
        print("Low is closest")
        return dt_low

    else:
        print("High is closest")
        return dt_high

>>> now = datetime.datetime.now()
>>> dts = [datetime.datetime.now() + datetime.timedelta(seconds=n * 20 - 5) for n in range(-2, 6)]
>>> for d in dts: print(d)
... 
2023-08-08 19:49:52.401911
2023-08-08 19:50:12.401925
2023-08-08 19:50:32.401926
2023-08-08 19:50:52.401927
2023-08-08 19:51:12.401928
2023-08-08 19:51:32.401929
2023-08-08 19:51:52.401930
2023-08-08 19:52:12.401934
>>> find_closest(dts, now)
High 7, low 0, center 3 - time at center is 2023-08-08 19:50:52.401927, offset of 22.224106
High 3, low 0, center 1 - time at center is 2023-08-08 19:50:12.401925, offset of 17.775896
High 3, low 1, center 2 - time at center is 2023-08-08 19:50:32.401926, offset of 2.224105
High is closest
datetime.datetime(2023, 8, 8, 19, 50, 12, 401925)
>>> next_dt = now + datetime.timedelta(seconds=80)
>>> find_closest(dts, next_dt)
High 7, low 0, center 3 - time at center is 2023-08-08 19:50:52.401927, offset of 57.775894
High 7, low 3, center 5 - time at center is 2023-08-08 19:51:32.401929, offset of 17.775892
High 7, low 5, center 6 - time at center is 2023-08-08 19:51:52.401930, offset of 2.224109
High is closest
datetime.datetime(2023, 8, 8, 19, 51, 32, 401929)
>>> next_dt - now
datetime.timedelta(seconds=80)
>>> find_closest(dts, next_dt) - find_closest(dts, now)
(...)
datetime.timedelta(seconds=80, microseconds=4)
>>> # (the takeaway is that floating points WILL make you age faster.)

Of course, unless you have tons of data to process and performance is a concern here, the simpler linear search approach is probably better, as it is way less code and easier to understand.

Also there's probably a better way with a more numerical approach like @user4581301 has suggested, using timedelta alongside with division, rounding, and multiplication, using rounding to your advantage to quantize the time to the 20 minute grid. But this approach has the upside that it works in general with any list of datetimes with any spacing, even irregular spacings, so if your datetimes isn't evenly spaced in 20 minute intervals it'd still work.