Skip to content

Instantly share code, notes, and snippets.

@gogsbread
Created January 5, 2013 05:28
Show Gist options
  • Save gogsbread/4459935 to your computer and use it in GitHub Desktop.
Save gogsbread/4459935 to your computer and use it in GitHub Desktop.
Non-Overlapping algorithm
using System;
using System.Collections.Generic;
namespace RandomMusings
{
public struct Range
{
public int start;
public int end;
public static List<Range> Merge(Range a, Range b)
{
List<Range> mergedRange = new List<Range>();
if(b.start > a.start && b.end < a.end){
mergedRange.Add(a);
}
else if(b.start > a.end)
{
mergedRange.Add(a);
mergedRange.Add(b);
}
else if(b.start > a.start && b.end > a.end)
{
Range r = new Range();
r.start = a.start;
r.end = b.end;
mergedRange.Add(r);
}
return mergedRange;
}
}
public class NonOverlapping
{
static void Main(){
int[] setArray = {0,3,1,5};
Stack<Range> mergedArray = new Stack<Range>();
for(int i = 0; i < setArray.Length ; i = i+2){
Range curRange = new Range();
curRange.start = setArray[i];
curRange.end = setArray[i+1];
if(mergedArray.Count > 0)
{
List<Range> result = Range.Merge(mergedArray.Pop(),curRange);
foreach(Range r in result)
mergedArray.Push(r);
}
else
mergedArray.Push(curRange);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment