How to know whether there is any overlap in a collection of periods using LINQ

Question

I have a collection of periods [FromDate, ToDate].

I would know whether there is any overlap between a given period and the periods in the collection.

I've already started with this:

 // periodToCheck is the given item
 bool conflict = Periods.Any(p => ((p.FromDate >= periodToCheck.fromDate && 
                                    p.FromDate <= periodToCheck.toDate)
                                  ||
                                   (p.ToDate >= periodToCheck.fromDate && 
                                    p.ToDate <= periodToCheck.toDate))
                             );

The problem that it does not cover all the situation, for example:

[2010.1.1], [2010.1.31]
[2010.1.5], [2010.1.6] // Is valid in the query in spite of it is not valid 
                       // (because there is intersection).

And if I discuss more situation I think the query will become more complicated.

I wonder if you could help me with the simplest valid way.

Regards.

Answer 1

Approach it this way instead: There is no intersaction if the check date's todate < the from date, or the check date's fromdate > the to date. This is assuming check.from <= check.to.

Periods.Any(p => !(check.ToDate < p.FromDate || check.FromDate > p.ToDate));

or (after unwrapping the negative):

Periods.Any(p => check.ToDate >= p.FromDate && check.FromDate <= p.ToDate));

Answer 2

If FromDate <= ToDate always holds true for your Period objects, you can define a helper extension method OverlapsWith as follows:

public static bool OverlapsWith(this Period a, Period b)
{
    return !(b.ToDate <= a.FromDate || a.ToDate <= b.FromDate);
}

To illustrate what's going on, let's look at the two cases where there is no overlap between a and b:

//                         a
//                |-----------------|
//   |--------|                          |-----------|
//       b1                                    b2

You can check the above condition against this diagram. Since the diagram shows the cases where no overlap occurs, but the method really ought to test for overlap, the condition needs to be negated. It could be simplified to the following:

           b.ToDate > a.FromDate && a.ToDate > b.FromDate

When you use this method in a LINQ query, it turns out very easy to understand:

    Periods.Any(period => period.OverlapsWith(periodToCheck))

Answer 3

You may find the following article useful and especially the TimePeriodIntersector class.

Sample excerpt:

public void TimePeriodIntersectorSample()
{
    TimePeriodCollection periods = new TimePeriodCollection();

    periods.Add( new TimeRange( new DateTime( 2011, 3, 01 ), new DateTime( 2011, 3, 10 ) ) );
    periods.Add( new TimeRange( new DateTime( 2011, 3, 05 ), new DateTime( 2011, 3, 15 ) ) );
    periods.Add( new TimeRange( new DateTime( 2011, 3, 12 ), new DateTime( 2011, 3, 18 ) ) );

    periods.Add( new TimeRange( new DateTime( 2011, 3, 20 ), new DateTime( 2011, 3, 24 ) ) );
    periods.Add( new TimeRange( new DateTime( 2011, 3, 22 ), new DateTime( 2011, 3, 28 ) ) );
    periods.Add( new TimeRange( new DateTime( 2011, 3, 24 ), new DateTime( 2011, 3, 26 ) ) );

    TimePeriodIntersector<TimeRange> periodIntersector = 
                    new TimePeriodIntersector<TimeRange>();
    ITimePeriodCollection intersectedPeriods = periodIntersector.IntersectPeriods( periods );

    foreach ( ITimePeriod intersectedPeriod in intersectedPeriods )
    {
        Console.WriteLine( "Intersected Period: " + intersectedPeriod );
    }
    // > Intersected Period: 05.03.2011 - 10.03.2011 | 5.00:00
    // > Intersected Period: 12.03.2011 - 15.03.2011 | 3.00:00
    // > Intersected Period: 22.03.2011 - 26.03.2011 | 4.00:00
} // TimePeriodIntersectorSample