Simple Java 2ms O(n) solution with clear comments beats 97.7%


  • 3
    W
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            List<Interval> res = new ArrayList<>();
            int n = intervals.size();
            // two corner cases to speed up the solution
            if (n == 0 || (intervals.get(0).start > newInterval.start && intervals.get(n-1).end < newInterval.end)) {
                res.add(newInterval);
                return res;
            }
            
            int index = 0;
            for(int i = 0; i < n; i++) { // three situations have to be considered
                if(intervals.get(i).end < newInterval.start) {
                    res.add(intervals.get(i));
                    index++;
                } else if(intervals.get(i).start > newInterval.end) {
                    res.add(intervals.get(i));
                } else { // when there is a overlap
                    newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
                    newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
                }
            }
            // add newInterval at the right place
            res.add(index, newInterval);
            return res;
        }

Log in to reply
 

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