4 ms Java solution, O(N), with comments


  • -1
    J
    public class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            List<Interval> output = new ArrayList<>();
            
            boolean added = false; // flag for marking if newInterval is added
            for (Interval in : intervals) {
                if (in.end < newInterval.start) { // left to newInterval
                    output.add(in);
                } else if (in.start <= newInterval.end && in.end >= newInterval.start) { // overlapping 
                    newInterval.start = Math.min(in.start, newInterval.start);
                    newInterval.end = Math.max(in.end, newInterval.end);
                } else { // right to newInterval
                    if (!added) { // insert the newInterval
                        output.add(newInterval);
                        added = true;
                    }
                    output.add(in);
                }
            }
            if (!added) output.add(newInterval);
            
            return output;
        }
    }

Log in to reply
 

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