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?


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

Fan mail

Multiple people with my name use my email address and I can read their email, chaos ensues!

Read more
Intelligent Trip

After years of building, our top-notch consultancy to help start-ups and scale-ups create great, scalable products, I think it is high time I added an update to how it is going and what's next for us.

Read more
Guest blog: Building, in partnership with communities by Shog9

A lesson in building communities by Stack Overflow's most prominent community manager emeritus, Shog9

Read more
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

Gleanings

hackurls - news for hackers and programmers
Claudio Santini • Mar 27, 2017

$ wget -O - hackurls.com/ascii | less

Read more…