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);

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.

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
                );