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.


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. ∎


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)
            prevEnd = DateTime.Parse(request.End);

    return ret;

And you, how did you solve it?


A software engineer & Stack Overflow alumnus. Co-founder of Badgie. I write about software development, coding, architecture and team leadership. I also speak at conferences worldwide.


Become my patreon

Join my discord


And the Most Realistic Developer in Fiction is...
Julia Silge • Mar 28, 2017

We can say that Mr. Robot is having a moment. The main character was one of the top choices and thus is perhaps the most/least realistic/annoying/inspiring portrayal of what it’s like to be a computer programmer today.

Read more…