Whats the fastest way to find a consecutive day list.

Question

i have an array of vacation dates. These are always going to be weekdays. Lets say

DateTime[] dates = new DateTime[] {"1/8/2010","1/3/2010","1/6/2010","1/7/2010","1/21/2010"}

i now have a single input date. Lets say:

DateTime vacationDateToCheck = 1/7/2010;

i want to find the vacation set (list of dates) given the set above. In particular, i want the first and last date of the list.

So for example, if i pass in vacationDateToCheck variable (1/7/2010) i would get back

Yes, you are on vacation from 1/6/2010 to 1/8/2010.

If i pass in 1/4/2010 it would return an empty result.

Here is the kicker. I want it to factor in weekends and go across weekends. So if i have a vacation on a friday and on the following Monday, i would want it to include that as one list.

any suggestions?

Answer 1

First, you'll have to sort your array, or at least make a sorted copy if it's important that you keep the order in the original list. If you don't, this isn't going to be easy.

Then, find the index of the element you're checking for. Once you've done that, create a loop going forwards, and one going backwards in your array, and count the date you've reached in the loop if the two dates are consective; otherwise, stop that loop (and do the other loop if you haven't done that already).

This assumes that all days in the range you're looking for can be found in the list, including weekends and holidays.

EDIT: If you want to include weekends implictly, you'll have to check the weekday using DayOfWeek while iterating over the days. The simplest way to do this is probably to also maintain a variable for the next expected day; every iteration in your loop, you add (or subtract, when moving backwards through the sorted array) one day. If the day you're processing is a Friday (or Monday when moving backwards), add/subtract an additional 2 days to skip the weekend.

Here's the basic idea (not tested, but you should get the point). I'm assuming that you've sorted dates already, and that you've found the initial date in your array (at index i). For simplicity, I'm also assuming that vacationDateToCheck is never a Saturday or Sunday; if it can be either of those, you'll have to adjust accordingly.

DateTime expectedDate = vacationDateToCheck.AddDays(1);
if (vacationDateToCheck.DayOfWeek == DayOfWeek.Friday)
  expectedDate = expectedDate.AddDays(2);
DateTime startDate = vacationDateToCheck;
DateTime endDate = vacationDateToCheck;
for (int j = i + 1; i < dates.Length; i++) {
  if (dates[i] == expectedDate) {
    endDate = dates[i];
    expectedDate = dates[i].AddDays(1);
    if (dates[i].DayOfWeek == DayOfWeek.Friday)
      expectedDate = expectedDate.AddDays(2);
  } 
  else 
  {
    break;
  }
}

Iterating the other way is similar, only you add -1 and -2 days instead, and you check if the day of the week is a Monday.

Answer 2

First of all, I would make a list of StartDay and a list of EndDay for each vacation. but lets go for your example:

1. Find if the day you requested exists in the list. (if the list was a dictionary you could have DateTime.Ticks as a key and find it in O(1).

2. if it does, look if NextDay = Day.AddDays(1.0) is in the list and look for PrevDay = Day.AddDays(-1.0) is in the list.

3. Repeat 2. until you find a date that is not in the list.