Answer for "Christmas visit nightmare"

TL;DR: Not only I did get an answer by an egregious reader (hi Emmet!), but it was a really good one.

The way to solve the problem is to use an algorithm known as "earliest deadline first": you sort by ascending end date and then proceed in order, excluding the family members that overlap.

Demonstration

It's fairly easy to convince ourselves that it returns a optimal solution by following this line of reasoning.

1. Sort the dates as specified above
2. pick the first element
3. Get all the visits that overlap with this visit.
   
   • Note that they will be all the visits that include the end date of the first element (and only those).
   • Note that at most one of these visits must be part of any optimal solution (as they overlap).

4. Let's prove that it's exactly one:There are two possibilities. Either this subset overlaps with the rest of the visits, or it does not.

   • If it doesn't, then it's evident that choosing any of the visits in the subset is fine for the purpose of creating an optimal solution.
   • If there is overlap, then clearly selecting one visit one visit that does not overlap is necessary to create an optimal solution.

   In both cases, of course, the best possible choice is our choice (it's the one the ends the earliest — leaves more days for the rest —and by construction it does not overlap with the rest of the set).

5. So, we've chosen our first visit and we must reject all the rest of the visit in the subset because of overlap.
6. We can then proceed in the same manner from point 2. with the rest of the set (pick in visits in the same way, exclude overlaps).

This is guaranteed to give us an optimal solution. ∎

Solutions

My solution implements this line of thought and uses recursion:

public IEnumerable<Relative> ScheduleVisits(IEnumerable<Relative> visitRequests)
{
    return SubSchedule(visitRequests.OrderBy(r => DateTime.Parse(r.End)));
}

private IEnumerable<Relative> SubSchedule(IEnumerable<Relative> input)
{
    if (!input.Any()) return input;
    var first = input.First();
    return new[] { first }.Union(SubSchedule(input.SkipWhile(r => DateTime.Parse(r.Start) < DateTime.Parse(first.End))));
}

His solution, instead uses a straight for loop. Much simpler!

public IEnumerable<Relative> ScheduleVisits(IEnumerable<Relative> visitRequests)
{
    var orderedByEnd = visitRequests.OrderBy(v => DateTime.Parse(v.End));

    var ret = new List<Relative>();
    var prevEnd = DateTime.MinValue;

    foreach (var request in orderedByEnd)
    {
        if (DateTime.Parse(request.Start) >= prevEnd)
        {
            ret.Add(request);
            prevEnd = DateTime.Parse(request.End);
        }
    }

    return ret;
}

And you, how did you solve it?