C# O(nlgn) solution


  • 0
    K

    Sort the intervals by start, and then end. Add the first interval to a new interval list. Then iterate through the rest of the sorted intervals list. if the interval starts before or at the new interval list's head end position, we can extend the interval, by taking the max of the end position.

    /**
     * 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) {
            if(intervals.Count == 0) {
                return new List<Interval>();
            }
            IList<Interval> list = intervals.OrderBy(x => x.start).ThenBy(x => x.end).ToList();
            
            IList<Interval> output = new List<Interval>();
            output.Add(new Interval(list[0].start, list[0].end));
            
            for(int i = 1; i < list.Count; ++i){
                Interval currInterval = output[output.Count - 1];
                if(currInterval.end >= list[i].start){
                    currInterval.end = Math.Max(currInterval.end, list[i].end);
                }
                else{
                    output.Add(new Interval(list[i].start, list[i].end));
                }
            }
            
            return output;
        }
    }
    

Log in to reply
 

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