Overlapping List of Objects

Question

I have the following

var list = new List<Schedule>();

Schedule object has the following properties:

• StartTime (DateTime)
• EndTime (DateTime)

Is there a one-line piece of code that can check if the time constraints overlap in list while iterating through all its Schedule members?

Thanks in advance.

I'm trying to have the logic of the above in a method called EnforceOverlapPolicy() that technically would throw a new exception if there are any conflicts.

Answer 1

If all you care about is whether an overlap exists and not which schedules overlap then you should be able to do this in O(n log n). The key is to sort the schedules by their StartTime and EndTime (the O(n log n) part). Then you can enumerate the result and compare each schedule's StartTime to the previous schedule's EndTime. If the StartTime is earlier than the EndTime then you have overlapping schedules. I do not think it can be done in a single query, however, without some third party help. I am a fan of Ix-Main myself. The following solution uses the Buffer function from Ix-Main:

bool hasOverlap =
    list
    .OrderBy(x => x.StartTime)
    .ThenBy(x => x.EndTime)
    .Buffer(2, 1)
    .Where(x => x.Count == 2)
    .Where(x => x[1].StartTime < x[0].EndTime)
    .Any();

If you do not want to use third party libraries then you can do the same thing with the following:

Schedule first = null;
bool hasOverlap = false;
using(var enumerator = list.OrderBy(x => x.StartTime).ThenBy(x => x.EndTime).GetEnumerator())
{
    enumerator.MoveNext();
    first = enumerator.Current;
    while(enumerator.MoveNext())
    {
        if(enumerator.Current.StartTime < first.EndTime)
        {
            hasOverlap = true;
            break;
        }
    }
}

Answer 2

Assuming performance is not an issue (otherwise consider an algorithm for overlaps):

var pairs = from f in list 
            from s in list
            where (f.EndTime < s.StartTime) && (f.StartTime < s.EndTime) && (f != s)
            select new {First = f, Second = s };

Basically, we're checking all possible pairs for overlap.

Alternatively, without query syntax:

var overlaps = list.SelectMany(l => list, (f, s) => new {f,s})
    .Where(x => (x.f.EndTime < x.s.StartTime) && 
               (x.f.StartTime < x.s.EndTime) && (x.f != x.s));

Answer 3

A different approach and I am not sure of the performance of the whole thing, but the idea is to flatten out the ranges defined by your schedules in a BitArray that signals if a specific minute has been already used by a previous schedule.

Technically it is also not a 'one liner' answer albeit from the stand point of the calling code it is just one line

So suppose to have defined a class ScheduleList

public class ScheduleList : List<Schedule>
{
    private BitArray ba = new BitArray(1440);

    // Define own Add method to Add a Schedule to the list
    // Or override the predefined one....
    public Schedule Add(int sh, int sm, int eh, int em)
    {
        Schedule s = new Schedule();
        s.StartTime = new DateTime(1, 1, 1, sh, sm, 0);
        s.EndTime = new DateTime(1, 1, 1, eh, em, 0);

        // Of course, having full control on the Add phase, you
        // could easily enforce your policy at this point. 
        // You could not accept a new schedule if the time slot is busy
        // but we could ignore it at this point

        this.Add(s);
        return s;
    }

    public bool IsTimeSlotBusy(Schedule s)
    {
        int sidx = Convert.ToInt32(TimeSpan.FromMinutes((s.StartTime.Hour * 60) + s.StartTime.Minute).TotalMinutes);
        int eidx = Convert.ToInt32(TimeSpan.FromMinutes((s.EndTime.Hour * 60) + s.EndTime.Minute).TotalMinutes);
        for (int x = sidx; x <= eidx; x++)
        {
            if (ba.Get(x)) return true;
            ba.Set(x, true);
        }
        return false;
    }
}

now you could write something like this

ScheduleList schedules = new ScheduleList();
schedules.Add(12, 0, 12, 30);
schedules.Add(15, 10, 15, 30);
schedules.Add(12, 0, 23, 59);
schedules.Add(14, 0, 23, 59);

// The fake 'one liner'
bool overlap = schedules.Any(s => schedules.IsTimeSlotBusy(s));
Console.WriteLine(overlap);

Waiting for the mathematicians here to show me why this is worst. (Not ironic, I really wish to know if this is bad from a mathematical point of view)

Answer 4

public static bool DoesNotOverlap(List<Schedule> timeSlots)
{
    DateTime endPrior = DateTime.MinValue;

    foreach (Schedule timeSlot in timeSlots.OrderBy(x => x.StartTime))
    {
        if (timeSlot.StartTime > timeSlot.EndTime || timeSlot.StartTime < endPrior)
            return false;
        endPrior = timeSlot.End;
    }

    return true;
}

For whoever needs this, it's not a one liner as the question requests but it is simple approach that solves the issue of checking for overlapping DateTime elements with Start and End date

1. Sort the list using OrderBy Linq operator.
2. Do not allow the beginning DateTime to be more than the ending DateTime.
3. Track the end of each previous meeting to see if it overlaps within the next start of the scheduled DateTime.