I originally wrote this challenge in 2012 to select a few developers for my previous company. They turned it down! I still think it's a nice puzzle. I would like to publish more in the future, let's see how this goes.

Instructions

Subsitute //Write code here... with your awesome solution. Feel happy.

If you want me to look at it, your answer to [email protected] (if you can't guess the email, there's a captcha waiting for you as a punishment). If you don't want me to look at it, that's ok, too. This is not a competition, but a past time.

Next week I'll publish a solution.

The Challenge

You have a very large family, and it seems that everybody wants to visit this Christmas! Unfortunately, you only have one guest room, so you can't accomodate more than one relative at any one time, but, since you love all your relatives equally, you want to get to see as many of them as possible.

Write a method which returns a list of relatives that lets you see most people without overlaps. Results are ordered by start date.

public IEnumerable<Relative> ScheduleVisits(IEnumerable<Relative> visitRequests) 
{  
    //Write code here... 
}

//Example input:
var input = new[]
    {
        new Relative {Name = "Aunt Alice", Start = "21-12-2012", End = "24-12-2012"},
        new Relative {Name = "Uncle Bob", Start = "23-12-2012", End = "26-12-2012"},
        new Relative {Name = "Cousin Charles", Start = "26-12-2012", End = "27-12-2012"},
        new Relative {Name = "Grannie Delia", Start = "24-12-2012", End = "25-12-2012"}
    };

//Example output:
var output = new[]
    {
        new Relative {Name = "Aunt Alice", Start = "21-12-2012", End = "24-12-2012"},
        new Relative {Name = "Grannie Delia", Start = "24-12-2012", End = "25-12-2012"},
        new Relative {Name = "Cousin Charles", Start = "26-12-2012", End = "27-12-2012"}
    };

There are two things I'd like to add: there is at least one edge case which is not included in the sample data. Can you identify it? Can you determine the big O of the algorithm you are producing? Can we make it better?