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;

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>();

IList<Interval> nonoverlapped = Merge(intervals);
Debug.Assert(nonoverlapped.start == 0 && nonoverlapped.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>();

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;
for (int i = 1; i < sortedIntervals.Count; i++)
{
Interval current = sortedIntervals[i];

/* Two intervals are not overlapped */
if(previous.end < current.start)
{
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

return nonOverlapped;
}
}
}
• 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. Jan 23 '17 at 5:11
• @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. Jan 23 '17 at 5:15
• Good. Nice question, kudos for taking the time to explain that :-) Jan 23 '17 at 5:16

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);
}
}
• The OP algorithm does not require two intervals with the same start to be sorted right. If sorted then why is Math.Min required? Jan 23 '17 at 17:55
• That was left over from a previous implementation.
– user33306
Jan 23 '17 at 18:05
• @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 Jan 23 '17 at 20:08
• 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. Jan 23 '17 at 20:14

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 */
previous = current;
}
else
{
/* merge two overlapped intervals */
previous = new Interval(previous.Start, Math.Max(previous.End, current.End));
}
}
return nonOverlapped;
}
• Leetcode online judge provides this hidden interface, and thank you to update us the Interval class should have better variable names. Jan 23 '17 at 20:17
• 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. Jan 23 '17 at 20:28
• @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. Jan 23 '17 at 21:01

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;
}
• 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. Jan 23 '17 at 18:48
• @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. Jan 26 '17 at 20:18

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).ToList(); // SORT INTERVALS BY START
for (int i=1;i<list.Count;i++)
if (list[i]<=list[i-1]) // interval2 starts before or at interval1 end
{
list[i-1]=Math.Max(list[i],list[i-1]); // merge
list.RemoveAt(i--); // delete redundant interval and backwards counter
}
return list.ToArray();
}