What am I missing in this algorithm to find a TimeOfDay between two TimeSpans that may span separate days?

Question

I have a List<T> of available times within a 24 hour day, and two TimeSpans, minTime and maxTime.

I need to find a time of day within the List<T> that lands between the minTime and maxTime, however due to this being used in multiple timezones, the minTime and maxTime can be on separate days and span something like 1pm to 1am the next day

The closest I've come to is this, but I feel like I am missing some major component here, or doing something really inefficient since I'm fairly new to the TimeSpan object. I just can't figure out what...

// Make new TimeSpan out of maxTime to eliminate any extra days (TotalHours >= 24),
// then check if time on the MaxTime is earlier than the MinTime
if (new TimeSpan(maxTime.Hours, maxTime.Minutes, maxTime.Seconds) < minTime)
{
    // If time on MaxTime is earlier than MinTime, the two times span separate days,
    // so find first time after minTime OR before maxTime
    nextAvailableTime = Times.FirstOrDefault(p =>
        (p.Time.TimeOfDay >= minTime || (p.Time.TimeOfDay < maxTime))
        && p.Count < ConcurrentAppointments);
}
else
{
    // If time on MaxTime is later than MinTime, the two times are for the same day
    // so find first time after minTime AND before maxTime
    nextAvailableTime = Times.FirstOrDefault(p =>
        (p.Time.TimeOfDay >= minTime && p.Time.TimeOfDay < maxTime)
        && p.Count < ConcurrentAppointments);
}

The List of Times uses EST (my local time), however the minTime and maxTime can be based on other time zones.

For example, if we ran this algorithm for a Hawaii time zone, we will end up having minTime = new TimeSpan(13, 0, 0) and maxTime = new TimeSpan(25, 0, 0), since 8am - 8pm HST = 1pm - 1am EST.

The Times collection is a List<AppointmentTime>, and AppointmentTime is a class looks like this:

class AppointmentTime
{
    DateTime Time { get; set; } 
    int Count { get; set; }
}

I'm fairly sure I'm missing something major here, or that there should be a more efficient way of doing this that I'm not aware of, but I really can't think of what it could be. Is there something wrong with my algorithm? Or a more efficient way of finding a TimeOfDay between two TimeSpans that may span separate days?

Update

I figured out what I was missing based on CasperOne's answer. I was forgetting the date actually does matter since my times are going across different time zones.

Using my above example of the Hawaii time zone, scheduling appointments for Monday would result in incorrectly scheduling Hawaii appointments on Sunday night.

My solution was to check that the previous day was valid before scheduling appointments for the "first window" of the 24-hour day, and to adjust the appointment date by .AddDays(maxTime.Days) when comparing with maxTime

// If time on MaxTime is earlier than MinTime, the two times span separate days,
// so find first time after minTime OR before maxTime if previous day has appointments set as well
var isPreviousDayValid = IsValidDate(AppointmentDate.AddDays(-1));

nextAvailableTime = Times.FirstOrDefault(p =>
    (p.Time.TimeOfDay >= minTime 
        || (p.Time.AddDays(maxTime.Days).TimeOfDay < maxTime && isPreviousDayValid)
    ) && p.Count < ConcurrentAppointments);

Saluki

@pst "Most efficient"? :) I have a solution that I think works... I just feel like its not optimized and there is a better way I'm missing due to being fairly unfamiliar with the TimeSpan object – Saluki

Better :) I'll let the title go on a technicality. – Immiscible

Can we assume if minDate is greater than maxDate that it indicates a window of time across two days? – Hijoung

@Hijoung minDate is never greater than maxDate, however minDate.Hours can be greater than maxDate.Hours, in which case yes it would indicate a window of time across more than one day – Saluki

Are minDate and maxDate DateTime structures with actual date components, or is the date irrelevant in them? If minTime is greater than maxTime that's the indicator that the window is on the next day? – Hijoung

@Hijoung They're TimeSpan objects, so the date is irrelevant however there are cases where you would have something like maxDate = new TimeSpan(25, 30, 0) because 8:30pm EST = 1:30am UTC – Saluki

So if the TimeSpan is more than one day, then you have a window that overlaps a day, got it. – Hijoung

Answer 1

The general idea is, don't compare times, compare dates; translate your windows from times to dates and the rest comes easy.

You can generate a new set of DateTime instances for each item in the list to compare the minimum and the maximum against, using the Date property as the base for calculating the caps on the range you want to compare against.

This assumes that your minTime is always less than maxTime, and if your window covers more than one day you represent the range overlapping into a new day by having an Hours property value on the TimeSpan that is greater than 24 hours.

You have to see if there's a window from the day before as well as the day after. For example:

   (1)  (2)  (3)  (4)  (5)
----x----x----x----x----x----

(1) - 1/1/1900 11:00 PM - Date component in your list - 1 day + min time
(2) - 1/2/1900 12:05 AM - this is the date and time from your list
(3) - 1/2/1900 01:00 AM - Date component in your list - 1 day + max time
(4) - 1/2/1900 11:00 PM - Date component in your list + min time
(5) - 1/3/1900 01:00 AM - Date component in your list + max time

This means that you need to create two windows and check to see that your in either:

nextAvailableTime = Times.FirstOrDefault(p => {
    // Check count first, get this out of the way.
    if (!(p.Count < ConcurrentAppointments)) return false;

    // The date time and the date component
    DateTime dt = p.Time;
    DateTime d = dt.Date;

    // The windows
    DateTime prevWindowMin = d.AddDays(-1) + minTime;
    DateTime prevWindowMax = d.AddDays(-1) + maxTime;
    DateTime windowMin = d + minTime;
    DateTime windowMax = d + maxTime;

    // Is it in *either* window;
    return
        (prevWindowMin <= dt && dt <= prevWindowMax)||
        (windowMin <= dt && dt <= windowMax);
});

It's not completely clear from your question, but if times of the day are something other than the Date component of the items in your list, you can substitute p.Time for the Date component of that date (subtracting a day as appropriate to create the windows) and it should work.

Hijoung

Thanks, I'll have to run some tests tomorrow to make sure this works and see how it compares to my current method, but your logic seems sound. (This is for scheduling thousands of appointments at once from all different time zones, so performance is important to me) – Saluki

@Saluki See the last paragraph (you might have missed it); if it's some other date, you can get that Date component and use that (which I imagine what you really have). That means you don't have to calculate the min and max DateTime windows every time. Regardless, on any decent machine, these operations should be trivial, even for thousands of items. – Hijoung

@rachel I must realized this is 1/2 if the solution, you also have to use the day before (as your time could lie in the overlap from the day before). That said, just use the current date and the prior date as a base and check between both those windows and you should be good. – Hijoung

@rachel updated the answer with a diagram of the windows you have to keep track of and the code you need to represent that. – Hijoung

Thanks for your answer, you helped me realize the part I was missing was the actual date. It does matter after all, as appointments are only scheduled M-F, and my current logic was allowing them to get set Saturday night – Saluki

Answer 2

@Rachel, can you provide an counterexample which makes this unusable?

nextAvailableTime = Times.OrderBy(i => i.Time).FirstOrDefault(i => i.Count < ConcurrentAppointments &&
    i.Time.TimeOfDay >= minTime &&
    i.Time.TimeOfDay < maxTime
            );

[EDIT]

So, the following should work. The way I understood it, the question is how to find efficiently the smallest TimeOfDay of the AppointmentTime, following the minimum between the TimeOfDay of the minTime and maxTime. For 1,000,000 iterations, Rachel's code runs in ~0.55 seconds

var Times = new List<AppointmentTime>();
var ConcurrentAppointments = 10;
Times.AddRange(new[]{
    new AppointmentTime()
    {
        Count = 0,
        Time = new DateTime(2012, 12, 1, 1, 30, 0)
    },
    new AppointmentTime()
    {
        Count = 0,
        Time = new DateTime(2012, 12, 1, 13, 5, 0)
    },
    new AppointmentTime()
    {
        Count = 0,
        Time = new DateTime(2012, 12, 1, 11, 0, 0)
    }});

var minTime = new TimeSpan(13, 0, 0);
var maxTime = new TimeSpan(25, 0, 0);

// Version 1
// Not so performant, ~0.48 seconds for a loop of 1,000,000 iterations, see Version 2

//nextAvailableTime = Times.OrderBy(i => i.Time).FirstOrDefault(i => i.Count < ConcurrentAppointments &&
//    i.Time.TimeOfDay.TotalSeconds >= Math.Min(maxTime.TotalSeconds % (3600 * 24), minTime.TotalSeconds)
//    );

// Version 2
// Better performance, ~0.12 seconds for 1,000,000 iterations. We calculate the 
// constant value we are comparing with outside the lambda expression

// We calculate the `totalSeconds` variable as the minimum of seconds within the 
// 24h day. For that, we use the `% (3600 * 24)` operation to exclude the days.
var totalSeconds = (int)Math.Min(maxTime.TotalSeconds % (3600 * 24), minTime.TotalSeconds);

// We create a timespan variable called `timeOfDay` which is based on the
// `totalSeconds` variable above. Note that the day is not essential.
var timeOfDay = (new DateTime(1, 1, 1, totalSeconds / 3600, (totalSeconds % 3600) / 60, totalSeconds % 60)).TimeOfDay;

// Returns the `AppointmentTime` with the 01:30 AM. Note, again, that the 
// date of the `AppointmentTime` is not essential
nextAvailableTime = Times.FirstOrDefault(i => i.Count < ConcurrentAppointments &&
                i.Time.TimeOfDay >= timeOfDay
                );

Cavour

That would not work in the case where minTime and maxTime end up falling on two separate dates, such as minTime = new TimeSpan(13, 0, 0) and maxTime = new TimeSpan(25, 0, 0) (8am - 8pm EST -> 1pm - 1am UTC) – Saluki

@Rachel, thanks for the feedback. What do you think about my update? – Cavour

Thanks for the updated answer, however I realized that I was missing checking for dates in my algorithm, not missing something with my actual syntax. Sorry for the confusing question, I blame it on it being a Friday at the end of a really long week, and my brain was feeling fried :) I knew I had something wrong, but I couldn't figure out what and mistakenly thought it had to do with the syntax I was using instead of the algorithm itself – Saluki