O(n) Java solution


  • 0
    F
    /**
     * Definition for an interval.
     * public class Interval {
     *     int start;
     *     int end;
     *     Interval() { start = 0; end = 0; }
     *     Interval(int s, int e) { start = s; end = e; }
     * }
     */
    public class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    
            int start = newInterval.start;
            int end = newInterval.end;
    
            List<Interval> result = new ArrayList<>();
            boolean newAdded = false;
    
            for (Interval in: intervals) {
    
                if (in.end < start) {
                    result.add(in);
                } else if (in.start > end) {
                    if (!newAdded) {
                      result.add(new Interval(start, end));
                      newAdded = true;
                    }
                    result.add(in);
                } else {
                    start = Math.min(in.start, start);
                    end = Math.max(in.end, end);
                }
            }
    
            if (!newAdded) {
                result.add(new Interval(start, end));
            }
    
            return result;
        }
    }
    

Log in to reply
 

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