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.


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?

Hi, I'm Marco Cecconi. I am the founder of Intelligent Hack, developer, hacker, blogger, conference lecturer. Bio: ex Stack Overflow core team, ex Toptal EM.

Read more

Newest Posts

Can you migrate a company from on-premise to remote-only?

Some lessons learned over the past 8 years of remote work in some of the best remote companies on the planet

Read more
Announcing Intelligent Cache, our caching library

Our newest open source initiative, intelligent cache, is available for use

Read more
Guest Blog: The mythical 10x programmer by Antirez

In this post, Salvatore Sanfilippo puts together a list of qualities that I believe make the most difference in programmers’ productivity.

Read more

Today I want to introduce our second engineering team: Team EMEA

Read more
Guest Blog: Technology and Storytelling by Orf Quarenghi

LEGO star-ships aren't made to collect dust on a shelf, but to explore strange new worlds

Read more


No, I Don’t Want to Subscribe to Your Newsletter
The Bureau of Programming • Feb 25, 2017

No, I don’t want to subscribe to your newsletter. No, I don’t want to complete a short survey. And no, I don’t want to become a member.

Read more…