CODEWITHSUNDEEP
c#javadate
RKodakandla
RKodakandla

Reputation: 3494

Given a list of Date ranges, how I do verify that all the days in a date range are covered in the list?

I have a list of date ranges.

05/01/2012 - 07/01/2012
07/02/2012 - 09/05/2012
01/01/2012 - 03/31/2012
08/01/2012 - 12/31/2012

Now the problem is to verify whether the given list covers all the dates in a specific range. For ex, this list covers all the dates in range 05/01/2012 - 12/31/2012, but non 01/01/2012-12/31/2012 because April dates are not covered in this list. Assumptions are,

  1. date range are valid - start date <= end date.
  2. Date ranges may overlap as in the case of 2nd and 4th above.
  3. List is not sorted in any way.

What I have so far is to test the outliers like,

Finding the smallest start date and largest end date - If the start and/or end date of your test date range are less/greater than these dates respectively, test fails.

But what is the best strategy to check for any missed dates in the middle? Thanks in advance!

Upvotes: 1

Views: 2228

Answers (5)

Peter Lawrey
Peter Lawrey

Reputation: 533710

The simplest strategy is to parse all the dates involved. O(N)

Sort the dates by the starting date. O(N log N) time

Compare the end date with the next start date (ignoring any end dates which go backwards) O(N)

If the one end to the next start date is more than a day you have a gap.

Upvotes: 3

Max
Max

Reputation: 4077

try something like the following (after sorting the list range by min date):-

  i=0
  a=min_date at 0 position
b=max_date corresponding to a

while list has elements
   c= min_date at (i+1) position
   d=max_date corresponding to c

if (b< (c - 1 day))
then there is a gap;
else 
{ 
if(b<d)   // done to handle the situation :- 06/07/2012 - 12/31/2012
          // 08/07/2012 - 11/31/2012. Then b will still remain 12/31/2012 after if condition
{
  b=d;
}
}
i=i+2;
end while;

The above will only find any missing date in the list.

Upvotes: 0

Guvante
Guvante

Reputation: 19223

The first thing to do is fix your input data.

  1. Order all ranges by start date
  2. Remove all overlaps by setting start dates
  3. Eliminate any ranges that disappear due to 2

So your ranges would become

01/01/2012 - 03/31/2012
05/01/2012 - 07/01/2012
07/02/2012 - 09/05/2012
09/06/2012 - 12/31/2012

Then you just have to find the missing dates, see if you can figure out how to do that.

Upvotes: 2

Slartibartfast
Slartibartfast

Reputation: 1623

Generate every date in the ranges, put them in a list and test to see if your candidate is in that list.

Upvotes: 0

Gilbert Le Blanc
Gilbert Le Blanc

Reputation: 51553

Convert the dates to the number of days since 1 January 1970 (or some other reference date).

Then your problem becomes find the missing integers.

Upvotes: 0

Related Questions