C# O(nlogn) solution, sort and loop


  • 0
    Y
    /**
     * 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; }
     * }
     */
    public class Solution {
        public IList<Interval> Merge(IList<Interval> intervals) {
            intervals=intervals.OrderBy(aa=>aa.start).ToList();
            int n = intervals.Count;
            if(n<2)
                return intervals;
            List<Interval> res = new List<Interval>();
            var newInt=intervals[0];
            for(int i=1;i<n;i++)
            {
                if(intervals[i].start<=newInt.end)
                {
                    newInt = new Interval(Math.Min(intervals[i].start,newInt.start),Math.Max(intervals[i].end,newInt.end));
                }
                else
                {
                    res.Add(newInt);
                    newInt=intervals[i];
                }
            }
            res.Add(newInt);
            return res;
        }
    }

  • 0
    Z

    @yanbinZhu If you sort it, how can the running time be O(n)?


  • 0
    Y

    you are right, this solution should be O(nlogn)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.