Leetcode 56: Merge Intervals

Question

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

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. — Phrancis, CommentedJan 23, 2017 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. — Jianmin Chen, CommentedJan 23, 2017 at 5:15
Good. Nice question, kudos for taking the time to explain that :-) — Phrancis, CommentedJan 23, 2017 at 5:16

score 1 · Accepted Answer · 2017-01-23 18:05:06Z

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? — paparazzo, CommentedJan 23, 2017 at 17:55
@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 — Jianmin Chen, CommentedJan 23, 2017 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. — Jianmin Chen, CommentedJan 23, 2017 at 20:14

paparazzo · Accepted Answer · 2017-01-23 11:44:00Z

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

Leetcode online judge provides this hidden interface, and thank you to update us the Interval class should have better variable names. — Jianmin Chen, CommentedJan 23, 2017 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. — Jianmin Chen, CommentedJan 23, 2017 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. — paparazzo, CommentedJan 23, 2017 at 21:01

bushed · Accepted Answer · 2017-01-24 10:44:54Z

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. — Dan Lyons, CommentedJan 23, 2017 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. — Jianmin Chen, CommentedJan 26, 2017 at 20:18

Zuabros · Accepted Answer · 2020-09-07 00:05:03Z

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

Stack Exchange Network

Leetcode 56: Merge Intervals

4 Answers 4

Linked

Hot Network Questions

Leetcode 56: Merge Intervals

4 Answers 4

Linked

Related

Hot Network Questions