trjhtr

I have a list of records containing Id, DateFrom, DateTo. For the sake of this question we can use this one:

List<(int, DateTime, DateTime)> data = new List<(int, DateTime, DateTime)>
 
 (1, new DateTime(2012, 5, 16), new DateTime(2018, 1, 25)),
 (2, new DateTime(2009, 1, 1), new DateTime(2011, 4, 27)),
 (3, new DateTime(2014, 1, 1), new DateTime(2016, 4, 27)),
 (4, new DateTime(2015, 1, 1), new DateTime(2015, 1, 3)),
 ;

In my real case the List could be a lot bigger, for now I assume that there is only one entry for a certain Id.

The task is to find the two records that has the longest time overlap and to return the ids and the number of days overlapped.

Which in this sample case means that these should be records 1 and 3, because 2 is not overlapping with anyone, and 4 overlaps for shorter time.

My implementation of this is the following:

 public (int, int, int) GetLongestElapsedPeriod(List<(int, DateTime, DateTime)> periods)
 
 int firstId = -1;
 int secondId = -1;
 int periodInDays = 0;

 foreach (var period in periods)
 
 var Id = period.Item1;
 var dateFrom = period.Item2;
 var dateTo = period.Item3;

 for (int i = 0; i < periods.Count; i++)
 
 if (Id != periods[i].Item1)
 
 var tempId = periods[i].Item1;
 var tempDateFrom = periods[i].Item2;
 var tempDateTo = periods[i].Item3;

 if (tempDateFrom < dateTo && tempDateTo > dateFrom)
 
 DateTime commonStartingDate = tempDateFrom > dateFrom ? tempDateFrom : dateFrom;
 DateTime commonEndDate = tempDateTo > dateTo ? dateTo : tempDateTo;

 var elapsedPeriod = commonEndDate - commonStartingDate;

 if ((int)elapsedPeriod.TotalDays > periodInDays)
 
 periodInDays = (int)elapsedPeriod.TotalDays;
 firstId = Id;
 secondId = tempId;
 
 
 
 
 
 return (firstId, secondId, periodInDays);
 

But I think this way is not very efficient and I'm looking for ideas to optimize this logic. Also, I suspect that this is variation of some more general algorithmic problem.

I am not a c# programmer.

Firstly, you use a for each and a nested for loop, but both of these are iterating through the same List. For consistency (and for the next comment to make sense), I suggest that you use for loops.

for (int i = 0; i < periods.Count; i++)

You could start i not from 0. but from your current location + 1 in the outer loop. The logic behind this is that you have already compared the pairs of periods previous to this - no need to double handle. Hence why using similar for loops will make this easier - you will be counting where you are in the List in the outer loop.

Making this small change means that if (Id != periods[i].Item1 is no longer needed - reducing one nesting level in the code.

As a 'meaningful name thing', I would call commonStartingDate and commonEndDate overlapStart and overlapEnd respectively - this is more descriptive of what you mean.
overlapStart = max(period1.Start, period2.Start)
overlapEnd = min(period1.End,period2.End)

Error checking: check that Item2 is always less than Item3 (and fix if not), otherwise your logic will be broken.

You could simplify var elapsedPeriod = commonEndDate - commonStartingDate and the following code by using:

int elapsedPeriod = (int)(commonEndDate - commonStartingDate).TotalDays 

May not look simpler above, but in the next block:

 if (elapsedPeriod > periodInDays)
 {
 periodInDays = elapsedPeriod;
 firstId = Id;
 secondId = tempId;

You don't use elapsedPeriod for anything else.

The main logic is good - I remember having to solve this problem 25 years ago when developing an accommodation booking database.