using System; using System.Collections.Generic; using System.Linq; public class Range { public int Start { get; private set; } public int End { get; private set; } public Range(int start, int end) { this.Start = (start <= end) ? start : end; this.End = (end >= start) ? end : start; } public bool Contains(int value) { if(value >= this.Start && value <= this.End) { return true; } return false; } public bool Overlaps(Range other) { if(other == null) { return false; } if(this.Contains(other.Start) || this.Contains(other.End) || other.Contains(this.Start) || other.Contains(this.End)) { return true; } return false; } public Range Merge(Range other) { if(!this.Overlaps(other)) { throw new ApplicationException("Can't merge two ranges."); } int newStart = (this.Start < other.Start) ? this.Start : other.Start; int newEnd = (this.End > other.End) ? this.End : other.End; return new Range(newStart, newEnd); } public static Range[] Merge(Range[] ranges) { Stack results = new Stack(); if(ranges != null) { Array.Sort(ranges, CompareRangeByStart); foreach(var range in ranges) { if(results.Count == 0) { results.Push(range); } else { var top = results.Peek(); if(top.Overlaps(range)) { var union = top.Merge(range); results.Pop(); results.Push(union); } else { results.Push(range); } } } } return results.Reverse().ToArray(); } private static int CompareRangeByStart(Range range1, Range range2) { return range1.Start - range2.Start; } } // ========================= Test Code ========================= public static class TestClass { private static bool AreEqual(Range[] ranges1, Range[] ranges2) { if(ranges1 == null && ranges2 == null) { return true; } if(ranges1 == null || ranges2 == null) { return false; } if(ranges1.Length != ranges2.Length) { return false; } for(int i = 0; i < ranges1.Length; ++i) { Range range1 = ranges1[i]; Range range2 = ranges2[i]; if(range1.Start != range2.Start || range1.End != range2.End) { return false; } } return true; } private static void Test(string testName, Range[] input, Range[] expected) { Range[] output = Range.Merge(input); if(AreEqual(output, expected)) { Console.WriteLine(string.Format("{0} passed", testName)); } else { Console.WriteLine(string.Format("{0} FAILED", testName)); } } private static void Test1() { Range[] input = new Range[] { new Range(5, 15), new Range(20, 30), new Range(35, 45), new Range(10, 25), new Range(30, 40) }; Range[] expected = new Range[] { new Range(5, 45) }; Test("Test1", input, expected); } private static void Test2() { Range[] input = new Range[] { new Range(5, 15), new Range(20, 30), new Range(35, 45), new Range(15, 15), new Range(50, 50) }; Range[] expected = new Range[] { new Range(5, 15), new Range(20, 30), new Range(35, 45), new Range(50, 50) }; Test("Test2", input, expected); } private static void Test3() { Range[] input = new Range[] { new Range(5, 15), new Range(35, 45), new Range(20, 30), }; Range[] expected = new Range[] { new Range(5, 15), new Range(20, 30), new Range(35, 45), }; Test("Test3", input, expected); } private static void Test4() { Range[] input = new Range[] { new Range(10, 25), new Range(30, 40), new Range(8, 10), new Range(32, 40) }; Range[] expected = new Range[] { new Range(8, 25), new Range(30, 40) }; Test("Test4", input, expected); } private static void Test5() { Range[] input = new Range[] { new Range(5, 13), new Range(27, 39), new Range(8, 19), new Range(31, 37) }; Range[] expected = new Range[] { new Range(5, 19), new Range(27, 39) }; Test("Test5", input, expected); } private static void Test6() { Range[] input = new Range[] { new Range(5, 13), new Range(27, 39) }; Range[] expected = new Range[] { new Range(5, 13), new Range(27, 39) }; Test("Test6", input, expected); } private static void Test7() { Range[] input = new Range[] { new Range(5, 13), new Range(5, 23), new Range(30, 43), new Range(30, 33) }; Range[] expected = new Range[] { new Range(5, 23), new Range(30, 43) }; Test("Test7", input, expected); } public static void Main() { Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); Test7(); } }