http://stackoverflow.com/questions/2244964/finding-number-of-overlaps-in-a-list-of-time-ranges
Given a list of time ranges, I need to find the maximum number of overlaps.
public class Interval<T> where T : IComparable{ public T Start { get; set; } public T End { get; set; } public Interval(T start, T end) { this.Start = start; this.End = end; }} public enum Mark { Start = 1, End = 2 } public int MaxNumberOfOverlap<T>(List<Interval<T>> input) where T : IComparable { List<KeyValuePair<T, Mark>> list = new List<KeyValuePair<T, Mark>>(); int len = input.Count; for (int i = 0; i < len; i++) { list.Add(new KeyValuePair<T, Mark>(input[i].Start, Mark.Start)); list.Add(new KeyValuePair<T, Mark>(input[i].End, Mark.End)); } list.Sort(this.Compare<T>); int count = 0; int maxCount = 0; foreach (var kp in list) { if (kp.Value == Mark.Start) { count++; if (count > maxCount) { maxCount = count; } } else { count--; } } return maxCount; } public Interval<T> MaxOverlapRange<T>(List<Interval<T>> input) where T : IComparable { List<KeyValuePair<T, Mark>> list = new List<KeyValuePair<T, Mark>>(); int len = input.Count; for (int i = 0; i < len; i++) { list.Add(new KeyValuePair<T, Mark>(input[i].Start, Mark.Start)); list.Add(new KeyValuePair<T, Mark>(input[i].End, Mark.End)); } list.Sort(this.Compare<T>); int count = 0; int maxCount = 0; Interval<T> result = null; T start = default(T); T end = default(T); bool flag = false; foreach (var kp in list) { if (kp.Value == Mark.Start) { count++; if (count > maxCount) { maxCount = count; start = kp.Key; flag = true; } } else { if (flag) { end = kp.Key; result = new Interval<T>(start, end); flag = false; } count--; } } return result; } private int Compare<T>(KeyValuePair<T, Mark> x, KeyValuePair<T, Mark> y) where T : IComparable { return x.Key.CompareTo(y.Key); }