C# O(n)


  • 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> Insert(IList<Interval> intervals, Interval newInterval) {
            intervals=intervals.ToList();
            int n=intervals.Count,i=0;
            List<Interval> res=new List<Interval>();
            for(;i<n;i++)
            {
                if(intervals[i].start>=newInterval.start)
                    break;
                res.Add(intervals[i]);
            }
            intervals.Insert(i,newInterval);
            if(i>0)
                res.Remove(res[i-1]);
            int j=i==0?0:i-1;
            for(;j<n;j++)
            {
                if(intervals[j].end>=intervals[j+1].start)
                {
                    intervals[j+1].start=Math.Min(intervals[j+1].start,intervals[j].start);
                    intervals[j+1].end=Math.Max(intervals[j+1].end,intervals[j].end);
                }
                else
                    res.Add(intervals[j]);
            }
            res.Add(intervals[n]);
            return res;
        }
    }

Log in to reply
 

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