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].

 

1 /** 2  * Definition for an interval. 3  * public class Interval { 4  *     public int start; 5  *     public int end; 6  *     public Interval() { start = 0; end = 0; } 7  *     public Interval(int s, int e) { start = s; end = e; } 8  * } 9  */10 11 public class IntervalComparer: IComparer
     
      12 {13     public int Compare(Interval x, Interval y)14     {15         return x.start != y.start ? x.start - y.start : x.end - y.end;16     }17 }18     19 public class Solution {20     public IList
      
        Merge(IList
       
         intervals) {21         if (intervals.Count < 2) return intervals;22         23         var list = intervals.ToList();24         25         list.Sort(new IntervalComparer());26         27         var result = new List
        
         ();28         29         for (int i = 0; i < list.Count; i++)30         {31             if (i == 0 || list[i].start > result[result.Count - 1].end)32             {33                 result.Add(list[i]);34             }35             else36             {37                 result[result.Count - 1].end = Math.Max(result[result.Count - 1].end, list[i].end);38             }39         }40         41         return result;42     }43 }