Algorithm to detect overlapping of dates in list

Question

I have list of records with start and end dates. I want to know which record dates overlap with other record dates. Below is the example, Record 5 dates overlap with records 3 and 4. How can I check this ?

I go through the link.

My question is because all the dates are in the same list, I have to take each record and compare against each other record which I think is a performance issue.

Is there any other way to do this ? like using Lambda ?

Do you have some code that you can show? Are your dates in a database? Wouldn't you rather express the logic in SQL? — sstan, Aug 17 '15 at 18:13
@sstan My dates are not from database. they are entered by user in textboxes. — Chatra, Aug 17 '15 at 18:14
How are your dates stored? As strings, DateTime objects, or something else? — Eric Dand, Aug 17 '15 at 18:19
possible duplicate of [How check intersection of DateTime periods](http://stackoverflow.com/questions/7325124/how-check-intersection-of-datetime-periods) — saarrrr, Aug 17 '15 at 18:19
Check out this lib: http://www.codeproject.com/Articles/168662/Time-Period-Library-for-NET — peco, Aug 17 '15 at 18:24
@saarrrr Not a duplicate. This one's asking to compare a list of dates rather than just comparing two. Also, Artem's answer below should be marked as the accepted answer; it works well. — Frank Tzanabetis, Apr 01 '16 at 04:16

score 3 · Answer 1 · answered Aug 17 '15 at 18:39

3

You simply need to sort the collection on the start date, and then the end date. After doing that you can iterate the collection and for each node you can look at the subsequent nodes until you find one that doesn't overlap.

So if your data set is already sorted this is an O(n) operation; if it's not sorted then it's an O(n*log(n)) operation which is still notably better than the O(n^2) time it would take for each node to be compared with each other node.

answered Aug 17 '15 at 18:39

Servy

202,030
26
332
449

1

I don't see how that works... {2,9001}, {3,9001},... {8999,9001} and overlap with {1,9000} - can you explain how you get less than O(n) on that one case or get O(n log n) for all (as there n^2 pairs of overlapping ranges)? – Alexei Levenkov Aug 17 '15 at 18:59
1

@AlexeiLevenkov Once it's sorted you just need to remember the latest end-date you've encountered, iterate the set, and if the current item starts after the end of the latest end date it overlaps with the previous group. You only need to iterate through the set once, after you've sorted it, and compare it against a value that you've already computed from previous iterations. – Servy Aug 17 '15 at 19:02
I see - you counting number of operations needed to *produce* the list, and I was counting number of operations to iterate output list (which could be much higher). I've deleted my post (as to be reasonable it needed way more details), consider providing pseudo-code / remark about complexity numbers in your post. – Alexei Levenkov Aug 17 '15 at 19:36

Artem Kulikov · Answer 2 · 2015-08-17T18:34:18.137

If you want to use LINQ - you can use this variant. But to be honest, for will give you better results in the context of performance. For example here you can find some comparison between for and LINQ and not in favor of LINQ

        var dates = new List<Tuple<DateTime, DateTime>>
                        {
                            new Tuple<DateTime, DateTime>(new DateTime(2001, 1, 1), new DateTime(2005, 1, 12)), 
                            new Tuple<DateTime, DateTime>(new DateTime(2006, 1, 1), new DateTime(2006, 4, 4)), 
                            new Tuple<DateTime, DateTime>(new DateTime(2007, 1, 5), new DateTime(2007, 10, 15)), 
                            new Tuple<DateTime, DateTime>(new DateTime(2009, 1, 2), new DateTime(2009, 4, 5)), 
                            new Tuple<DateTime, DateTime>(new DateTime(2007, 3, 3), new DateTime(2009, 5, 3))
                        };

        var overlaps = (from t1 in dates
                        from t2 in dates
                        where !Equals(t1, t2) // Don’t match the same object.
                        where t1.Item1 <= t2.Item2 && t1.Item2 >= t2.Item1   //check intersections
                        select t2).Distinct();

Algorithm to detect overlapping of dates in list

2 Answers2