Leetcode 56: Merge Intervals

Question

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: 
     * 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. 
     * 
     * Use LINQ to sort the intervals - 
     * http://stackoverflow.com/questions/15486/sorting-an-ilist-in-c-sharp
     */
    public static IList<Interval> Merge(IList<Interval> intervals)
    {
        IList<Interval> nonOverlapped = new List<Interval>(); 
        if(intervals == null || intervals.Count == 0)
        {
            return nonOverlapped; 
        }

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

        Interval previous = sortedIntervals[0];
        for (int i = 1; i < sortedIntervals.Count; i++)
        {
            Interval current = sortedIntervals[i]; 

            /* Two intervals are not overlapped */
            if(previous.end < current.start)
            {
                nonOverlapped.Add(previous);
                previous = current;
                continue;
            }

            /* merge two overlapped intervals, previous interval's start is 
               smaller than current's start */
            previous = new Interval(previous.start, Math.Max(previous.end, current.end)); 
        }

        // edge case 
        nonOverlapped.Add(previous); 

        return nonOverlapped; 
    }             
  }
}

Answer 1

I would suggest that a custom comparer would work better than orderby, since 2 intervals with the same start won't necessarily get sorted right:

public IList<Interval> Merge(IList<Interval> intervals)
{
    var outVal = new SortedSet<Interval>(intervals,new IntervalComparer());
    for (int i = 0; i < outVal.Count - 1; i++)
    {
        Interval curr = outVal.ElementAt(i);
        Interval next = outVal.ElementAt(i + 1);
        if(next.start - curr.end < 1)
        {
            curr.end = Math.Max(curr.end, next.end);
            outVal.Remove(next);
            i--;
        }
    }
    return outVal.ToList();
}
public class IntervalComparer : IComparer<Interval>
{
    public int Compare(Interval lhs, Interval rhs)
    {
        if (lhs.start == rhs.start)
        {
            return lhs.end.CompareTo(rhs.end);
        }
        return lhs.start.CompareTo(rhs.start);
    }
}

Answer 2

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<Interval> sortedEnumerable = intervals.OrderBy(f => f.start);
 IList<Interval> sortedIntervals = sortedEnumerable.ToList();

I think this is cleaner

public static IList<Interval> Merge(IList<Interval> intervals)
{
    IList<Interval> nonOverlapped = new List<Interval>();
    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;
}     

Answer 3

Given something like that at work and depending on the usage/location I'd suggest making Interval generic:

public class Interval<T> where T : IComparable<T>
{
    public T Start { get; set; }
    public T End { get; set; }
}

Also it would make sense to stream through resulting interval instead of holding 2 copies of all of them in memory. In this case Merge would have a different signature

IEnumerable<Interval<T>> Merge<T>(IEnumerable<Interval<T>> intervals) where T : IComparable<T>

and inside the body of that method you can use yield return and yield break operator to enumerate resulting intervals. Method would look like

IEnumerable<Interval<T>> Merge<T>(IEnumerable<Interval<T>> intervals) where T : IComparable<T>
{
    if(intervals == null) yield break;

    Interval<T> currentMerged = null;

    foreach (var interval in intervals.OrderBy(_ => _.Start))
    {
        if (currentMerged == null)
        {
            currentMerged = interval;
            continue;
        }

        if (currentMerged.End.CompareTo(interval.Start) < 0)
        {
            yield return currentMerged;
            currentMerged = interval;
            continue;
        }

        if (currentMerged.End.CompareTo(interval.End) < 0)
            currentMerged.End = interval.End;
    }

    if(currentMerged != null) yield return currentMerged;
}

Answer 4

Using a list allows just excluding redundant intervals. I think it is cleaner. The trick is backwarding the counter when you remove an element. Some people say against using "Math.Max", but the execution time difference is negligible and makes the code much easier to read.

public int[][] Merge(int[][] inter) {
var list = inter.OrderBy(x=>x[0]).ToList(); // SORT INTERVALS BY START
for (int i=1;i<list.Count;i++)
    if (list[i][0]<=list[i-1][1]) // interval2 starts before or at interval1 end
    {
        list[i-1][1]=Math.Max(list[i][1],list[i-1][1]); // merge
        list.RemoveAt(i--); // delete redundant interval and backwards counter
    }
return list.ToArray();
}