56. Merge Intervals

原题

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

代码实现

first, sort by start for every interval asc.
Then, discuss every interval’s end point.

public IList<Interval> Merge(IList<Interval> intervals)
        {
            if(intervals.Count==0|| intervals.Count==1) return intervals;
            var rtn = new List<Interval>();
            var s = intervals.OrderBy(r => r.start).ToList();
            rtn.Add(s[0]);
            for (int i = 1; i < s.Count; i++)
            {
                //analysis and discuss every interval's end point
                //overlap wholely
                if (rtn[rtn.Count - 1].end >= s[i].end)
                {
                    continue;
                }
                //overlap partly
                else if (rtn[rtn.Count - 1].end >= s[i].start)
                {
                    rtn[rtn.Count-1].end = s[i].end;
                }
                else //no overlap
                {
                    rtn.Add(s[i]);
                }           
            }
            return rtn;
        }

题库

Leetcode算法题目解决方案每天更新在github库中，欢迎感兴趣的朋友加入进来，也欢迎star，或pull request。https://github.com/jackzhenguo/leetcode-csharp