Car Rental Optimization

Question

Inspired by this r/dailyprogrammer post, the task is too calculate which records to use in order to serve the most records without any of the records having overlapping time spans.

I accomplish this goal by sorting the list of records by their total days spanned, then by iterating over each element and adding it to a new list as long as that record does not overlap with any records already within the "optimized" list.

The source,

internal class Program
{
    private static void Main(string[] args)
    {
        var rentalRecords = RentalRecordLoader.Load("rentals.txt");
        var result = RentalRecordOptimizer.CalculateMostEfficientRecords(rentalRecords);

        Console.WriteLine($"Total Records: {result.Count}");
        result.ForEach(r => Console.WriteLine($"{r.StartDay} : {r.EndDay}"));
    }
}

public class RentalRecord
{
    public int StartDay { get; set; }
    public int EndDay { get; set; }

    public RentalRecord(int startDay, int endDay)
    {
        StartDay = startDay;
        EndDay = endDay;
    }

    public int TotalDays()
    {
        return EndDay - StartDay;
    }

    public bool Overlapping(RentalRecord rentalRecord)
    {
        return StartDay <= rentalRecord.EndDay &&
            rentalRecord.StartDay <= EndDay;
    }
}

public abstract class RentalRecordLoader
{
    public static List<RentalRecord> Load(string path)
    {
        int recordCount;
        int[] startDays;
        int[] endDays;
        using (var reader = new StreamReader(path))
        {
            recordCount = int.Parse(reader.ReadLine());
            startDays = ConvertStringToIntArray(reader.ReadLine());
            endDays = ConvertStringToIntArray(reader.ReadLine());
        }

        var rentalList = new List<RentalRecord>();
        for (var i = 0; i < recordCount; i++)
        {
            rentalList.Add(new RentalRecord(startDays[i], endDays[i]));
        }

        return rentalList;
    }

    // Load() helper method
    private static int[] ConvertStringToIntArray(
        string value, string delimeter = " ")
    {
        return value.Trim().Split(delimeter)
                .Select(x => int.Parse(x))
                .ToArray();
    }
}

public abstract class RentalRecordOptimizer
{
    public static List<RentalRecord> CalculateMostEfficientRecords(
        List<RentalRecord> rentals)
    {
        var efficientRentals = new List<RentalRecord>();
        foreach (var rental in rentals.OrderBy(x => x.TotalDays()))
        {
            // Cant have any overlapping days.
            // The car cant be in two places at once.
            if (efficientRentals.Any(x => x.Overlapping(rental)))
            {
                continue;
            }
            efficientRentals.Add(rental);
        }
        return efficientRentals;
    }
}

The input used (stored in rentals.txt)

10
1 2 5 12 13 40 30 22 70 19
23 10 10 29 25 66 35 33 100 65

And the output:

Total Records: 5
5 : 10
30 : 35
13 : 25
40 : 66
70 : 100

Optimizations and better code design is obviously welcome, but I also had a specific question as well.

1. What would be the best way to handle incorrectly formatted data in
   rentals.txt? Just catch the exception in the Load function?

Answer 1

Before answering the question I have a few convention suggestions for you:

1. Use static instead f abstract when creating static classes. By the look of your code I assume that your classes are not mean to be used for creating new instances but using abstract to achieve this is ill advised since you can walk around the restriction by creating a class which inherits from this class. Instead use the static keyword to create your static class:

   public static class MyStaticClass
   {
       //static members here
   }
   

2. The method total days could be refactored as a property just with a getter method like this:

   public int TotalDays => EndDay - StartDay;
   

3. You could also use the Linq method Zip() to join the input lines into the record object

With Zip() you can turn this

var rentalList = new List<RentalRecord>();

for (var i = 0; i < recordCount; i++)
{
    rentalList.Add(new RentalRecord(startDays[i], endDays[i]));
}

return rentalList;

into this:

return startDays.Zip(endDays, (startDay, endDay) 
    => new RentalRecord(startDay, endDay)); 

---

Now for your question: I suggest validating the content of the file instead of letting it fail without having code explaining why it fail and then throw your own custom exception when the validation method fails. I'd refactor your Load method like this:

public static List<RentalRecord> Load(string path)
{
    int recordCount;
    int[] startDays;
    int[] endDays;
    using (var reader = new StreamReader(path))
    {
        if(!int.TryParse(out recordCount))
        {
            throw new MyInvalidCustomException("Record line is not in the 
            correct format);
        }
        startDays = ConvertStringToIntArray(reader.ReadLine());
        endDays = ConvertStringToIntArray(reader.ReadLine());
        if(startDays.Length != endDays.Length)
        {
            throw new MyInvalidCustomException("not all records have 
            matching start and end days");
        }
    }

    return startDays.Zip(endDays, (startDay, endDay) 
    => new RentalRecord(startDay, endDay)); 
}

This gives you a more specific exception control so you can troubleshoot the errors better.