## Wednesday, May 11, 2016

### MaxNumberOfOverlap MaxOverlapRange

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);`
`    ``}`