❔ Which of these two "best-fit" algorithms are better?
First one using binary search:
https://paste.mod.gg/jcpadjmvfxcb/0
or the one I did before the binary search which i find way easier to read
private static List<int> FindOptimalUnits(LocalDate requestedStartDate, LocalDate requestedEndDate, int requestedQty, Dictionary<int, IPeriod[]> units)
{
var accommodationGapSize = new Dictionary<int, int>();
foreach (var unit in units)
{
var currentClosestEndDate = LocalDate.MinIsoValue;
var currentClosestStartDate = LocalDate.MaxIsoValue;
foreach (var period in unit.Value)
{
if (period.EndDate <= requestedStartDate && period.EndDate > currentClosestEndDate)
{
currentClosestEndDate = period.EndDate;
}
if (period.StartDate >= requestedEndDate && period.StartDate < currentClosestStartDate)
{
currentClosestStartDate = period.StartDate;
}
if (currentClosestEndDate == requestedStartDate && currentClosestStartDate == requestedEndDate)
{
break; // Cannot find a better
}
}
var gapSize = Period.Between(currentClosestEndDate, currentClosestStartDate, PeriodUnits.Days).Days;
accommodationGapSize.Add(unit.Key, gapSize);
}
foreach (var item in accommodationGapSize)
{
Console.WriteLine(item.Value);
}
return accommodationGapSize.OrderBy(x => x.Value).Take(requestedQty).Select(x => x.Key).ToList();
}
}
private static List<int> FindOptimalUnits(LocalDate requestedStartDate, LocalDate requestedEndDate, int requestedQty, Dictionary<int, IPeriod[]> units)
{
var accommodationGapSize = new Dictionary<int, int>();
foreach (var unit in units)
{
var currentClosestEndDate = LocalDate.MinIsoValue;
var currentClosestStartDate = LocalDate.MaxIsoValue;
foreach (var period in unit.Value)
{
if (period.EndDate <= requestedStartDate && period.EndDate > currentClosestEndDate)
{
currentClosestEndDate = period.EndDate;
}
if (period.StartDate >= requestedEndDate && period.StartDate < currentClosestStartDate)
{
currentClosestStartDate = period.StartDate;
}
if (currentClosestEndDate == requestedStartDate && currentClosestStartDate == requestedEndDate)
{
break; // Cannot find a better
}
}
var gapSize = Period.Between(currentClosestEndDate, currentClosestStartDate, PeriodUnits.Days).Days;
accommodationGapSize.Add(unit.Key, gapSize);
}
foreach (var item in accommodationGapSize)
{
Console.WriteLine(item.Value);
}
return accommodationGapSize.OrderBy(x => x.Value).Take(requestedQty).Select(x => x.Key).ToList();
}
}
2 Replies
Any glaring issues or missed edge cases?
or this
private static List<int> FindOptimalUnitsThree(LocalDate requestedStartDate, LocalDate requestedEndDate, int requestedQty, Dictionary<int, IPeriod[]> units)
{
var accommodationGapSize = new Dictionary<int, int>();
foreach (var unit in units)
{
var closestLeft = unit.Value.LastOrDefault(y => y.EndDate <= requestedStartDate)?.EndDate ?? LocalDate.MinIsoValue;
var closestRight = unit.Value.FirstOrDefault(y => y.StartDate >= requestedEndDate)?.StartDate ?? LocalDate.MaxIsoValue;
var gapSize = Period.Between(closestLeft, closestRight, PeriodUnits.Days).Days;
accommodationGapSize.Add(unit.Key, gapSize);
}
foreach (var item in accommodationGapSize)
{
Console.WriteLine(item.Value);
}
return accommodationGapSize.OrderBy(x => x.Value).Take(requestedQty).Select(x => x.Key).ToList();
}
private static List<int> FindOptimalUnitsThree(LocalDate requestedStartDate, LocalDate requestedEndDate, int requestedQty, Dictionary<int, IPeriod[]> units)
{
var accommodationGapSize = new Dictionary<int, int>();
foreach (var unit in units)
{
var closestLeft = unit.Value.LastOrDefault(y => y.EndDate <= requestedStartDate)?.EndDate ?? LocalDate.MinIsoValue;
var closestRight = unit.Value.FirstOrDefault(y => y.StartDate >= requestedEndDate)?.StartDate ?? LocalDate.MaxIsoValue;
var gapSize = Period.Between(closestLeft, closestRight, PeriodUnits.Days).Days;
accommodationGapSize.Add(unit.Key, gapSize);
}
foreach (var item in accommodationGapSize)
{
Console.WriteLine(item.Value);
}
return accommodationGapSize.OrderBy(x => x.Value).Take(requestedQty).Select(x => x.Key).ToList();
}
Looks like nothing has happened here. I will mark this as stale and this post will be archived until there is new activity.