Find overlapping time periods (events) with LINQ

Question

I have a list of events and now I want to find out which events do overlap. Below you find the code I currently have, but I've the problem that the item which is searched for is also included in the list.

List<SomeEventObject> overlappingEvents = new List<SomeEventObject>();
foreach (SomeEventObject eventItem in EventList)
{
    bool overlapping = false;
    foreach (SomeEventObject anotherEventItem in EventList)
    {
        if (eventItem.StartDate <= anotherEventItem.EndDate &&
            eventItem.EndDate >= anotherEventItem.StartDate)
        {
            overlapping = true;
            overlappingEvents.Add(anotherEventItem);
        }
    }

    if (overlapping)
        overlappingEvents.Add(eventItem);
}

I would need to create a new list without the item searched for. Therefore I'm asking if there is a nice LINQ expression which can handle that for me. This is some pseudo code I thought of:

EventList.Where(e => 
                eventItem.StartDate <= e.EndDate && 
                eventItem.EndDate >= e.StartDate);

In this context eventItem doesn't exist of course.

As a result I think I would need two lists: one with overlapping events and one with non-overlapping events. But that should be possible with .Except() if I have my overlapping event list.

Edit:

I've created a dotnetfiddle so that one can play with it. One important question is the overlapping algorithm.

Event 1:
StartDate: today, 10:00
EndDate: today, 10:05

Event 2:
StartDate: today, 10:05
EndDate: today, 10:10

If you present this to the user then this is NOT overlapping. So I've to revise my algorithm.

Answer 1

I would do it this way:

var overlappingEvents =
(
    from e1 in EventList
    from e2 in EventList
    where e1 != e2
    where e1.StartDate <= e2.EndDate
    where e1.EndDate >= e2.StartDate
    from e in new [] { e1, e2 }
    select e
).ToList();

I think that should be quite straight forward.

---

As per the comment, this version only returns an EventList element once regardless of how many overlaps it participates in.

var overlappingEvents =
(
    from e1 in EventList
    where EventList
        .Where(e2 => e1 != e2)
        .Where(e2 => e1.StartDate <= e2.EndDate)
        .Where(e2 => e1.EndDate >= e2.StartDate)
        .Any()
    select e1
).ToList();

It can also be written as:

var overlappingEvents =
    EventList
        .Where(e1 =>
            EventList
                .Where(e2 => e1 != e2)
                .Where(e2 => e1.StartDate <= e2.EndDate)
                .Where(e2 => e1.EndDate >= e2.StartDate)
                .Any())
        .ToList();

---

Based on the further comment, here's how to pair the events:

var overlappingEvents =
(
    from e1 in EventList
    from e2 in EventList
    where e1 != e2
    where e1.StartDate <= e2.EndDate
    where e1.EndDate >= e2.StartDate
    select new [] { e1, e2 }
).ToList();

Now overlappingEvents is a list of arrays - List<SomeEventObject[]> and not List<SomeEventObject>. The array contains the overlapping events.

Answer 2

I'd try something like this:

var searchedFor = EventList.First(); // Replace by the proper one

var overlapping = EventList.Where(e => e != searchedFor && 
    EventList.Any(ev => e != ev && ev.StartDate <= e.EndDate && ev.EndDate >= e.StartDate))

// Alternatively with Except

var overlapping = EventList.Except(new[] { searchFor }).Where(e => 
    EventList.Any(ev => e != ev && ev.StartDate <= e.EndDate && ev.EndDate >= e.StartDate))

For the non-overlapping you simply filter the overlapping events from your EventList using Except:

var nonOverlapping = EventList.Except(overlappingEvents);

I don't know your SomeEventObject but you may need to change the inequality comparison by some Id comparison.

There is a quite good Q&A on detecting overlapping periods in C# that you may want to look into. You can also factor out the check as follows for convenience:

Func<SomeEventObject, SomeEventObject, bool> areOverlapped = (e1, e2) => 
    e1.StartDate <= e2.EndDate && e1.EndDate >= e2.StartDate;

var overlapping = EventList.Where(e => e != searchedFor && 
    EventList.Any(ev => e != ev && areOverlapped(e, ev)));

Answer 3

You can get the result with this:

var nonOverlappingEvents = EventList.Where(e1 => !EventList.Where(e2 => e2 != e1).Any(e2 => e1.StartDate <= e2.EndDate && e1.EndDate >= e2.StartDate));

But I do not understand your overlapping algorithm. I believe overlap means that StartDate of one event is between StartDate and EndDate of another one:

    var nonOverlappingEvents = EventList.Where(e1 => !EventList.Where(e2 => e2 != e1).Any(e2 => e2.StartDate >= e1.StartDate && e2.StartDate <= e1.EndDate));

Answer 4

I know you said you want to use Linq and it is certainly reasonably straight forward. We used to do that - however we do a lot of date range work and found a much better way of doing it.

If you are doing a lot of this time of work I would recommend the Itenso Time Period Library (available on Nuget).

It has support for a very rich range of time based operations. Such as IsSamePeriod, HasInside, OverlapsWith, or IntersectsWith are available for period relations.

It also support time collections e.g. All events for a person. These are based on ITimePeriodCollection can hold arbitrary elements of type ITimePeriod and interprets the earliest start of all its elements as the start of the collection time period. Correspondingly, the latest end of all its elements serves as the end of the collection period.

Some code example for a flavour of how it works

  //Setup a time range
TimeRange timeRange1 = new TimeRange(
        new DateTime( 2011, 2, 22, 14, 0, 0 ),
        new DateTime( 2011, 2, 22, 18, 0, 0 ) );
      Console.WriteLine( "TimeRange1: " + timeRange1 );
      // > TimeRange1: 22.02.2011 14:00:00 - 18:00:00 | 04:00:00

  // --- Setu uptime range 2 ---
  TimeRange timeRange2 = new TimeRange(
    new DateTime( 2011, 2, 22, 15, 0, 0 ),
    new TimeSpan( 2, 0, 0 ) );
  Console.WriteLine( "TimeRange2: " + timeRange2 );
  // > TimeRange2: 22.02.2011 15:00:00 - 17:00:00 | 02:00:00


  // --- relation ---
  Console.WriteLine( "TimeRange1.GetRelation( TimeRange2 ): " +
                     timeRange1.GetRelation( timeRange2 ) );

  // --- intersection ---
  Console.WriteLine( "TimeRange1.GetIntersection( TimeRange2 ): " +
                     timeRange1.GetIntersection( timeRange2 ) );
  // > TimeRange1.GetIntersection( TimeRange2 ):
  //             22.02.2011 15:00:00 - 17:00:00 | 02:00:00

Answer 5

Not with linq but groups overlaping periods into sets:

public class Range
{
    public DateTime Start { get; set; }
    public DateTime Stop { get; set; }

    public Range(DateTime start, DateTime stop)
    {
        Start = start;
        Stop = stop;
    }
}

void Main()
{
    List<Range> ranges = new List<Range>();
    ranges.Add(new Range(new DateTime(2019, 10, 1), new DateTime(2019, 10, 2)));
    ranges.Add(new Range(new DateTime(2019, 10, 2), new DateTime(2019, 10, 3)));
    ranges.Add(new Range(new DateTime(2019, 10, 1), new DateTime(2019, 10, 3)));
    ranges.Add(new Range(new DateTime(2019, 10, 4), new DateTime(2019, 10, 5)));
    ranges.Add(new Range(new DateTime(2019, 10, 6), new DateTime(2019, 10, 8)));
    ranges.Add(new Range(new DateTime(2019, 10, 5), new DateTime(2019, 10, 7)));
    ranges.Add(new Range(new DateTime(2019, 10, 9), new DateTime(2019, 10, 9)));

    var rangesOrdered = ranges.OrderBy(t => t.Start).ToList();

    var sets = new List<List<Range>>() { new List<Range>() {rangesOrdered[0]}};
    var IsOverlaping = new Func<Range, Range, bool>((a, b) => a.Start < b.Stop && b.Start < a.Stop);


    for (var i = 1; i < rangesOrdered.Count; i++)
    {
            if (IsOverlaping(sets.Last().OrderBy(s => s.Stop).Last(), rangesOrdered[i]))
            {
                sets.Last().Add(rangesOrdered[i]);
            }
            else
            {
                sets.Add(new List<Range>() {rangesOrdered[i]});
            }
    }
}