Leetcode 56: Merge Intervals

Problem statement


Given a collection of intervals, merge all overlapping intervals.


For example:


Given \$[1,3],[2,6],[8,10],[15,18]\$,


return \$[1,6],[8,10],[15,18]\$.

My introduction of algorithm:

I worked on the algorithm several times before, and then also studied a few of "merge intervals" questions on this site, found a sibling question - Finding the total time elapsed in the union of time intervals. The two problems are very similar, my working solution for Leetcode \$56\$ is also \$O(nlogn)\$ time by first sorting the input interval start time, then do a linear scan of the sorted array.

I spent more than one hour to practice again and passed all test cases through leetcode online judge, but I tried three times. First time I forgot to add edge case, after the for loop, Leetcode online judge showed me that the test case with one interval only failed, and then, I did not use sorted intervals in the code and then failed test cases with two intervals \$[1,4]\$,\$[0,4]\$ by returning \$[1,4]\$. Through practice, I added those two test cases in the code as well to remind me the importance of those two bases cases.

Also, I took more than five minutes to look up C# Comparator and then decided to use LINQ to sort the intervals, with a quick study of a Stack Overflow post. I'm still trying to figure out quickest way to sort in a C# implementation.

```
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; }
}

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

/*
* Test case:

Don't use lower case for public and don't us single letters in ctor

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; }
 }

Why create a List?

IEnumerable sortedEnumerable = intervals.OrderBy(f => f.start);
 IList sortedIntervals = sortedEnumerable.ToList();

I think this is cleaner

public static IList Merge(IList intervals)
{
    IList nonOverlapped = new List();
    if (intervals == null || intervals.Count == 0)
    {
        return nonOverlapped;
    }
    Interval previous = null;
    foreach (Interval current in intervals.OrderBy(f => f.Start))
    {                
        if(previous == null)
        {
            previous = current;
        }
        else if (current.Start > previous.End)
        {
            /* Two intervals are not overlapped */
            nonOverlapped.Add(previous);
            previous = current;
        }
        else
        {
            /* merge two overlapped intervals */
            previous = new Interval(previous.Start, Math.Max(previous.End, current.End));
        }
    }
    nonOverlapped.Add(previous);
    return nonOverlapped;
}

StackExchange Code Review Q#153355, answer score: 4