C# O(n) solution


  • 0
    H
    public IList<Interval> Insert(IList<Interval> intervals, Interval newInterval) {
            List<Interval> results = new List<Interval>();
            int i = 0;
            while(i < intervals.Count && intervals[i].end < newInterval.start) results.Add(intervals[i++]);
            
            int start = newInterval.start;
            int end = newInterval.end;
            while(i < intervals.Count && intervals[i].start <= end) {
                start = Math.Min(start, intervals[i].start);
                end = Math.Max(end, intervals[i++].end);
            }
            
            results.Add(new Interval(start, end));
            
            while(i < intervals.Count) results.Add(intervals[i++]);
            
            return results;
        }
    

Log in to reply
 

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