fork(4) download
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. public class Range
  6. {
  7. public int Start { get; private set; }
  8. public int End { get; private set; }
  9.  
  10. public Range(int start, int end)
  11. {
  12. this.Start = (start <= end) ? start : end;
  13. this.End = (end >= start) ? end : start;
  14. }
  15.  
  16. public bool Contains(int value)
  17. {
  18. if(value >= this.Start && value <= this.End)
  19. {
  20. return true;
  21. }
  22.  
  23. return false;
  24. }
  25.  
  26. public bool Overlaps(Range other)
  27. {
  28. if(other == null)
  29. {
  30. return false;
  31. }
  32.  
  33. if(this.Contains(other.Start) || this.Contains(other.End)
  34. || other.Contains(this.Start) || other.Contains(this.End))
  35. {
  36. return true;
  37. }
  38.  
  39. return false;
  40. }
  41.  
  42. public Range Merge(Range other)
  43. {
  44. if(!this.Overlaps(other))
  45. {
  46. throw new ApplicationException("Can't merge two ranges.");
  47. }
  48.  
  49. int newStart = (this.Start < other.Start) ? this.Start : other.Start;
  50. int newEnd = (this.End > other.End) ? this.End : other.End;
  51.  
  52. return new Range(newStart, newEnd);
  53. }
  54.  
  55. public static Range[] Merge(Range[] ranges)
  56. {
  57. Stack<Range> results = new Stack<Range>();
  58. if(ranges != null)
  59. {
  60. Array.Sort(ranges, CompareRangeByStart);
  61.  
  62. foreach(var range in ranges)
  63. {
  64. if(results.Count == 0)
  65. {
  66. results.Push(range);
  67. }
  68. else
  69. {
  70. var top = results.Peek();
  71. if(top.Overlaps(range))
  72. {
  73. var union = top.Merge(range);
  74. results.Pop();
  75. results.Push(union);
  76. }
  77. else
  78. {
  79. results.Push(range);
  80. }
  81. }
  82. }
  83. }
  84.  
  85. return results.Reverse().ToArray();
  86. }
  87.  
  88. private static int CompareRangeByStart(Range range1, Range range2)
  89. {
  90. return range1.Start - range2.Start;
  91. }
  92. }
  93.  
  94. // ========================= Test Code =========================
  95. public static class TestClass
  96. {
  97. private static bool AreEqual(Range[] ranges1, Range[] ranges2)
  98. {
  99. if(ranges1 == null && ranges2 == null)
  100. {
  101. return true;
  102. }
  103.  
  104. if(ranges1 == null || ranges2 == null)
  105. {
  106. return false;
  107. }
  108.  
  109. if(ranges1.Length != ranges2.Length)
  110. {
  111. return false;
  112. }
  113.  
  114. for(int i = 0; i < ranges1.Length; ++i)
  115. {
  116. Range range1 = ranges1[i];
  117. Range range2 = ranges2[i];
  118. if(range1.Start != range2.Start || range1.End != range2.End)
  119. {
  120. return false;
  121. }
  122. }
  123.  
  124. return true;
  125. }
  126.  
  127. private static void Test(string testName, Range[] input, Range[] expected)
  128. {
  129. Range[] output = Range.Merge(input);
  130. if(AreEqual(output, expected))
  131. {
  132. Console.WriteLine(string.Format("{0} passed", testName));
  133. }
  134. else
  135. {
  136. Console.WriteLine(string.Format("{0} FAILED", testName));
  137. }
  138. }
  139.  
  140. private static void Test1()
  141. {
  142. Range[] input = new Range[]
  143. {
  144. new Range(5, 15),
  145. new Range(20, 30),
  146. new Range(35, 45),
  147. new Range(10, 25),
  148. new Range(30, 40)
  149. };
  150.  
  151. Range[] expected = new Range[]
  152. {
  153. new Range(5, 45)
  154. };
  155.  
  156. Test("Test1", input, expected);
  157. }
  158.  
  159. private static void Test2()
  160. {
  161. Range[] input = new Range[]
  162. {
  163. new Range(5, 15),
  164. new Range(20, 30),
  165. new Range(35, 45),
  166. new Range(15, 15),
  167. new Range(50, 50)
  168. };
  169.  
  170. Range[] expected = new Range[]
  171. {
  172. new Range(5, 15),
  173. new Range(20, 30),
  174. new Range(35, 45),
  175. new Range(50, 50)
  176. };
  177.  
  178. Test("Test2", input, expected);
  179. }
  180.  
  181. private static void Test3()
  182. {
  183. Range[] input = new Range[]
  184. {
  185. new Range(5, 15),
  186. new Range(35, 45),
  187. new Range(20, 30),
  188. };
  189.  
  190. Range[] expected = new Range[]
  191. {
  192. new Range(5, 15),
  193. new Range(20, 30),
  194. new Range(35, 45),
  195. };
  196.  
  197. Test("Test3", input, expected);
  198. }
  199.  
  200. private static void Test4()
  201. {
  202. Range[] input = new Range[]
  203. {
  204. new Range(10, 25),
  205. new Range(30, 40),
  206. new Range(8, 10),
  207. new Range(32, 40)
  208. };
  209.  
  210. Range[] expected = new Range[]
  211. {
  212. new Range(8, 25),
  213. new Range(30, 40)
  214. };
  215.  
  216. Test("Test4", input, expected);
  217. }
  218.  
  219. private static void Test5()
  220. {
  221. Range[] input = new Range[]
  222. {
  223. new Range(5, 13),
  224. new Range(27, 39),
  225. new Range(8, 19),
  226. new Range(31, 37)
  227. };
  228.  
  229. Range[] expected = new Range[]
  230. {
  231. new Range(5, 19),
  232. new Range(27, 39)
  233. };
  234.  
  235. Test("Test5", input, expected);
  236. }
  237.  
  238. private static void Test6()
  239. {
  240. Range[] input = new Range[]
  241. {
  242. new Range(5, 13),
  243. new Range(27, 39)
  244. };
  245.  
  246. Range[] expected = new Range[]
  247. {
  248. new Range(5, 13),
  249. new Range(27, 39)
  250. };
  251.  
  252. Test("Test6", input, expected);
  253. }
  254.  
  255. private static void Test7()
  256. {
  257. Range[] input = new Range[]
  258. {
  259. new Range(5, 13),
  260. new Range(5, 23),
  261. new Range(30, 43),
  262. new Range(30, 33)
  263. };
  264.  
  265. Range[] expected = new Range[]
  266. {
  267. new Range(5, 23),
  268. new Range(30, 43)
  269. };
  270.  
  271. Test("Test7", input, expected);
  272. }
  273.  
  274. public static void Main()
  275. {
  276. Test1();
  277. Test2();
  278. Test3();
  279. Test4();
  280. Test5();
  281. Test6();
  282. Test7();
  283. }
  284. }
Success #stdin #stdout 0.03s 34016KB
stdin
Standard input is empty
stdout
Test1 passed
Test2 passed
Test3 passed
Test4 passed
Test5 passed
Test6 passed
Test7 passed