8
\$\begingroup\$

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; 
    }             
  }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ The reason it was on hold is because you said the code is failing some cases, in other words it doesn't work correctly. Code posted here must work as intended to be on topic. \$\endgroup\$ – Phrancis Jan 23 '17 at 5:11
  • \$\begingroup\$ @Phrancis, I did tell a story which is failed twice, last time succeeded. And also try to get some ideas through code review, people know where my weakness was through the practice failed trials. \$\endgroup\$ – Jianmin Chen Jan 23 '17 at 5:15
  • 1
    \$\begingroup\$ Good. Nice question, kudos for taking the time to explain that :-) \$\endgroup\$ – Phrancis Jan 23 '17 at 5:16
1
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • \$\begingroup\$ The OP algorithm does not require two intervals with the same start to be sorted right. If sorted then why is Math.Min required? \$\endgroup\$ – paparazzo Jan 23 '17 at 17:55
  • \$\begingroup\$ That was left over from a previous implementation. \$\endgroup\$ – tinstaafl Jan 23 '17 at 18:05
  • \$\begingroup\$ @tinstaafl, the above solution in theory should be a better solution compared to LINQ OrderBy, since SortedSet underneath uses binary search tree with O(nlogn) time complexity, but OrderBy may go up to O(n*n). Although Leetcode gave me different results, OrderBy solution is 518ms, but Comparator solution takes 712ms, 835ms. Code is here for my test, gist.github.com/jianminchen/7a2778829ccb31210d8850e581a99048 \$\endgroup\$ – Jianmin Chen Jan 23 '17 at 20:08
  • \$\begingroup\$ Using IComparer and also SortedSet are good combination of practice in sorting, and also merge overlapped intervals in the above code is also very clever by removing one interval and changing another interview's end value. First time I read the idea, probably most of us are new to the idea as well. \$\endgroup\$ – Jianmin Chen Jan 23 '17 at 20:14
3
\$\begingroup\$

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;
}     
\$\endgroup\$
  • \$\begingroup\$ Leetcode online judge provides this hidden interface, and thank you to update us the Interval class should have better variable names. \$\endgroup\$ – Jianmin Chen Jan 23 '17 at 20:17
  • \$\begingroup\$ I learned one idea a time. You taught me something here using Iterator of IList with LINQ in one statement. Great teaching. I voted another one but I wish I could vote two. \$\endgroup\$ – Jianmin Chen Jan 23 '17 at 20:28
  • 1
    \$\begingroup\$ @JianminChen The accepted solution is not more efficient than this and did nothing to review your code. That custom comparer provides NO value over sort on start. It still requires math.Max on end. \$\endgroup\$ – paparazzo Jan 23 '17 at 21:01
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You may want your null check to also check for the case where intervals is empty. As it is coded now, when intervals is empty, you'll return a single null element. Aside from that, I like the idea of using yields. \$\endgroup\$ – Dan Lyons Jan 23 '17 at 18:48
  • \$\begingroup\$ @bushed, I am still learning your code. I like the idea of using yields as well. I will put together a working code using your ideas and post the link here. \$\endgroup\$ – Jianmin Chen Jan 26 '17 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.