I have a list of contracts that has a timespan to be finished in. Some contracts are more important than others. If there is an overlap between two contracts we cut down the less important one in a way that will either cut in two, cut it from the start or the end or fully remove it.
My problem is: I've implemented the algorithm but I still have some minor errors which cause a false output.
e.g.
Input:
Start Ende Preis Priorität
1.1.2020 1.3.2020 20,40 1
1.2.2020 31.12.2020 18,00 2
1.6.2020 1.9.2020 16,90 3
Output should be:
Start Ende Preis
1.1.2020 31.1.2020 20,40
1.2.2020 31.5.2020 18,00
1.6.2020 1.9.2020 16,90
2.9.2020 31.12.2020 18,00
My Code:
List<Contract> contractList = //get value based on a file and get sorted based on the priority;
List<Contract> resultContracts = new List<Contract>()
{
contractList[0]
};
int n = contractList.Count;
for (var i = 0; i < contractList.Count; i++)
{
var lastProcessedContract = contractList[i]; // high priority
var contractsToRemove = new List<Contract>();
var contractsToAdd = new List<Contract>();
for (var j = i + 1; j < contractList.Count; j++){
var lessPriorityContract = contractList[j];
if (contractList[j].priority == contractList[i].priority)
{
continue;
}
if (lessPriorityContract.start >= lastProcessedContract.start && lessPriorityContract.end <= lastProcessedContract.end)
/*
* ------------------------>
* ------>
* oder
* ------------------------>
* -------->
* oder
* ------------------------->
* ------->
* oder
* --------------------------->
* --------------------------->
*/
{
contractsToRemove.Add(lessPriorityContract);
}
else if ((lessPriorityContract.start < lastProcessedContract.start
&& (lessPriorityContract.end > lastProcessedContract.start && lessPriorityContract.end <= lastProcessedContract.end)) ||
((lastProcessedContract.start < lessPriorityContract.end && lastProcessedContract.start > lessPriorityContract.start)
&& lastProcessedContract.end > lessPriorityContract.end))
/*
* ------------------------>
* ------>
* oder
* ------------------------------->
* ----------------------------------->
// oder
* -------------->
* ------------------------>
*/
{
lessPriorityContract.end = lastProcessedContract.start.AddDays(-1);
resultContracts.Add(lessPriorityContract);
}
else if (((lessPriorityContract.start < lastProcessedContract.end && lessPriorityContract.start >= lastProcessedContract.start)
&& lessPriorityContract.end > lastProcessedContract.end) || (lastProcessedContract.start < lessPriorityContract.start &&
(lastProcessedContract.end > lessPriorityContract.start && lastProcessedContract.end < lessPriorityContract.end)))
/*
* -------------------->
* ------------------------->
* oder
* -------------------->
* ---------------------------------->
*
//oder
* ------------>
* ------------------->
*
*/
{
lessPriorityContract.start = lastProcessedContract.end.AddDays(1);
resultContracts.Add(lessPriorityContract);
}
else if(lessPriorityContract.start < lastProcessedContract.start
&& lessPriorityContract.end > lastProcessedContract.end)
/*
* ------------>
* --------------------------->
* oder
* --------------------------->
* --------------------------->
*
*/
{
contractsToRemove.Add(lessPriorityContract);
var contract = new Contract
{
start = lessPriorityContract.start,
end = lastProcessedContract.start.AddDays(-1),
priority = lessPriorityContract.priority,
price = lessPriorityContract.price
};
contractsToAdd.Add(contract);
//contractList.Remove(contractList[i]);
//contractList.Add(contract);
resultContracts.Add(contract);
contract = new Contract
{
start = lastProcessedContract.end.AddDays(1),
end = lessPriorityContract.end,
priority = lessPriorityContract.priority,
price = lessPriorityContract.price
};
resultContracts.Add(contract);
contractsToAdd.Add(contract);
//contractList.Add(contract);
}
else
{
resultContracts.Add(lessPriorityContract);
}
}
foreach (var contractToRemove in contractsToRemove)
{
contractList.Remove(contractToRemove);
resultContracts.Remove(contractToRemove);
}
foreach (var contractToAdd in contractsToAdd)
{
contractList.Add(contractToAdd);
}
contractList.Sort();
}
resultContracts.Sort(new ContractComparer()); // Sorting based on start time of the contract
resultContracts = resultContracts.Distinct().ToList();
foreach (var flatElement in resultContracts)
{
Console.WriteLine(flatElement.ToString());
Console.WriteLine();
}
resultContracts.Sort();
Console.WriteLine("-------------------------------");
foreach (var flatElement in resultContracts)
{
Console.WriteLine(flatElement.ToString());
Console.WriteLine();
}
The Class Contract has attributes(start, end, price, priority) and an overridden Method from Icomparable to help sort based on priority.
I am open to get new efficient and faster algorithms too, otherwise repairing this would be also helpful.
edit: small notice is I am not concerned right now on how many attributes I am outputting as long as I solve the algorithm I can take care of that :)
I recommend taking a step back and generalizing first. At the core your problem is about "cutting" a date range based on another date range. So let's solve that first:
public record DateRange(DateTime From, DateTime To) {
public bool Overlaps(DateRange other) => From <= other.To && other.From <= To;
public IEnumerable<DateRange> Cut(DateRange other) {
if (!Overlaps(other)) {
yield return this;
} else if (From >= other.From && To > other.To) {
yield return this with { From = other.To.AddDays(1) };
} else if (From < other.From && To <= other.To) {
yield return this with { To = other.From.AddDays(-1) };
} else if (From < other.From && To > other.To) {
yield return this with { To = other.From.AddDays(-1) };
yield return this with { From = other.To.AddDays(1) };
}
}
}
Now we have a type for date ranges and an operation on them called "cut" which can shorten, split, or completely "remove" a date range based on its overlap with another date range. Or it will leave the date range as is when there is no overlap. I'll add the test class to the end of this answer as a proof of work.
Because we're working with not only two, but possibly many more date ranges from contracts, we can add another method to DateRange in order to help us:
public IEnumerable<DateRange> CutAll(IEnumerable<DateRange> others) => others
.Aggregate(
Enumerable.Repeat(this, 1),
(cuts, other) => cuts.SelectMany(s => s.Cut(other)));
This will split a date range into lots of "sub date ranges" if it overlaps with multiple others.
Your business code now boils down to:
Here's an example how this might look like in (untested) code:
var contracts = new List<Contract> {
new(Period: new(From: new(2020, 01, 01), To: new(2020, 03, 01)), Price: 20.40m, Priority: 1),
new(Period: new(From: new(2020, 02, 01), To: new(2020, 12, 31)), Price: 18.00m, Priority: 2),
new(Period: new(From: new(2020, 06, 01), To: new(2020, 09, 01)), Price: 16.90m, Priority: 3)
};
for (var i = 0; i < contracts.Count; i++) {
var current = contracts[i];
var successors = contracts[(i + 1)..];
var subDateRanges = current.Period.CutAll(successors.Select(c => c.Period));
foreach (var dr in subDateRanges) {
Console.WriteLine($"{dr.From} {dr.To} {current.Price} {current.Priority}");
}
}
public record Contract(DateRange Period, decimal Price, int Priority);
namespace Tests;
using FluentAssertions;
using Xunit;
public static class DateRangeTests {
public class Overlaps {
[Fact]
public void ReturnsFalseWhenRangesDontOverlap1() =>
Range("2019-01-01", "2019-01-15")
.Overlaps(Range("2019-01-20", "2019-01-31"))
.Should().BeFalse();
[Fact]
public void ReturnsFalseWhenRangesDontOverlap2() =>
Range("2019-01-20", "2019-01-31")
.Overlaps(Range("2019-01-01", "2019-01-15"))
.Should().BeFalse();
[Fact]
public void ReturnsTrueWhenRangesOverlap1() =>
Range("2019-01-01", "2019-01-20")
.Overlaps(Range("2019-01-15", "2019-01-31"))
.Should().BeTrue();
[Fact]
public void ReturnsTrueWhenRangesOverlap2() =>
Range("2019-01-15", "2019-01-31")
.Overlaps(Range("2019-01-01", "2019-01-20"))
.Should().BeTrue();
[Fact]
public void ReturnsTrueWhenRangesOverlap3() =>
Range("2019-01-01", "2019-01-31")
.Overlaps(Range("2019-01-10", "2019-01-20"))
.Should().BeTrue();
[Fact]
public void ReturnsTrueWhenRangesOverlap4() =>
Range("2019-01-10", "2019-01-20")
.Overlaps(Range("2019-01-01", "2019-01-31"))
.Should().BeTrue();
}
public class Cut {
[Fact]
public void ReturnsLeftSideWhenRightSideDoesNotOverlap() =>
Range("2019-01-01", "2019-01-10")
.Cut(Range("2019-01-20", "2019-01-31"))
.Should().ContainSingle().Which.Should().Be(Range("2019-01-01", "2019-01-10"));
[Fact]
public void AbsorbsLeftSideWhenRightSideOverlapsCompletely() =>
Range("2019-01-10", "2019-01-20")
.Cut(Range("2019-01-01", "2019-01-31"))
.Should().BeEmpty();
[Fact]
public void MovesStartOfLeftSideWhenRightSideOverlapsBeginning() =>
Range("2019-01-10", "2019-01-20")
.Cut(Range("2019-01-01", "2019-01-15"))
.Should().ContainSingle().Which.Should().Be(Range("2019-01-16", "2019-01-20"));
[Fact]
public void MovesEndOfLeftSideWhenRightSideOverlapsEnd() =>
Range("2019-01-10", "2019-01-20")
.Cut(Range("2019-01-15", "2019-01-25"))
.Should().ContainSingle().Which.Should().Be(Range("2019-01-10", "2019-01-14"));
[Fact]
public void SplitsLeftSideWhenRightSideIsInside() =>
Range("2019-01-01", "2019-01-31")
.Cut(Range("2019-01-15", "2019-01-25"))
.Should().SatisfyRespectively(
dr1 => dr1.Should().Be(Range("2019-01-01", "2019-01-14")),
dr2 => dr2.Should().Be(Range("2019-01-26", "2019-01-31")));
}
public class CutAll {
[Fact]
public void CutsLeftSideByAllFromRightSide() =>
Range("2019-02-01", "2019-02-28")
.CutAll([Range("2019-01-01", "2019-02-03"), Range("2019-02-10", "2019-02-15"), Range("2019-02-25", "2019-03-31")])
.Should().SatisfyRespectively(
dr1 => dr1.Should().Be(Range("2019-02-04", "2019-02-09")),
dr2 => dr2.Should().Be(Range("2019-02-16", "2019-02-24")));
[Fact]
public void ReturnsLeftSideWhenRightSideIsEmpty() =>
Range("2019-02-01", "2019-02-28")
.CutAll([])
.Should().ContainSingle().Which.Should().Be(Range("2019-02-01", "2019-02-28"));
}
private static DateRange Range(string from, string to) => new(DateTime.Parse(from), DateTime.Parse(to));
}