Leetcode 56 - Merge intervals - using C# SortedSet to sort intervals, define Comparator - Julia learned a few things through the code.

Leetcode56_MergeInterval_SortedSet.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MergeIntervals
{   
    class Program
    {
        /**
         * Definition for an interval.
         */
        public class Interval
        {
            public int start;
            public int end;
            public Interval() { start = 0; end = 0; }
            public Interval(int s, int e) { start = s; end = e; }
        }

        /*
         * IntervalComparer is to compare the interval start value, but if
         * the two have the same value, then compare end value. 
         * 
         */
        public class IntervalComparer : IComparer<Interval>
        {
            public int Compare(Interval leftHandSide, Interval rightHandSide)
            {
                if (leftHandSide.start == rightHandSide.start)
                {
                    return leftHandSide.end.CompareTo(rightHandSide.end);
                }

                return leftHandSide.start.CompareTo(rightHandSide.start);
            }
        }

        static void Main(string[] args)
        {
            RunSampleTestcase1();
            RunSampleTestcase2();
        }

        /*
         * Test case: 
         * help to test intervals should be sorted first before merging. 
         * [1,4], [0,4] should not be [1,4]
         */
        public static void RunSampleTestcase1()
        {
            IList<Interval> intervals = new List<Interval>();
            intervals.Add(new Interval(1, 4));
            intervals.Add(new Interval(0, 4));

            IList<Interval> nonoverlapped = Merge(intervals);
            Debug.Assert(nonoverlapped[0].start == 0 && nonoverlapped[0].end == 4);
        }

        /*
         * Test case: 
         * help to test that edge case is handled properly . 
         * [1,4] should be [1,4], not []
         * In other words, there is one interval in the input, the result should be itself. 
         * For loop 
         */
        public static void RunSampleTestcase2()
        {
            IList<Interval> intervals = new List<Interval>();
            intervals.Add(new Interval(1, 4));

            IList<Interval> nonoverlapped = Merge(intervals);
            Debug.Assert(nonoverlapped.Count == 1);
        }

        /*
         * Merge all overlapping intervals
         * Output: all intervals are non-overlapped. 
         * 
         * Sort intervals using binary search tree, O(nlogn) algorithm. 
         * Go over intervals from start smallest to bigger ones, check two intervals, denoting
         * current, next. 
         * 
         * If two intervals do not have overlapped, then do nothing. Otherwise, 
         * set current interval to maximum of two intervals' end, and remove
         * next interval. 
         * 
         * source code from code review post:
         * http://codereview.stackexchange.com/a/153418/123986
         */
        public static IList<Interval> Merge(IList<Interval> intervals)
        {
            var sortedIntervals = new SortedSet<Interval>(intervals, new IntervalComparer());

            for (int i = 0; i < sortedIntervals.Count - 1; i++)
            {
                Interval current = sortedIntervals.ElementAt(i);
                Interval next    = sortedIntervals.ElementAt(i + 1);

                // two intervals are overlapped
                if (next.start - current.end < 1)
                {
                    // set current interval's end, and then remove next interval
                    current.end = Math.Max(current.end, next.end);
                    sortedIntervals.Remove(next); 

                    i--; // go back to old index, continue
                }
            }

            return sortedIntervals.ToList();
        }        
    }
}