fork(5) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Test1 passed
Test2 passed
Test3 passed
Test4 passed
Test5 passed
Test6 passed
Test7 passed
https://ideone.com/kg4TwM
Merge Ranges
language:
C# (gmcs 5.20.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!