Easy to understand Java solution (beats 69%)


  • 0
    M
    /**
     * 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) {
            List<Interval> result = new ArrayList<>();
            
            // tells us if we are in the process of overlapping one or multiple intervals
            boolean overlap = false;
            
            // special case where intervals has no elements
            if (intervals.size()==0)  {
                result.add(newInterval);
                return result;
            }
            
            // special case where newInterval is non-overlapping and is the first interval
            if (newInterval.end < intervals.get(0).start) {
                result.add(newInterval);
            }
            
            for (int i=0; i<intervals.size(); i++) {
                Interval in = intervals.get(i);
                
                // if newInterval is overalapping (4 cases) with the current interval
                if (newInterval.start<=in.end&&newInterval.end>in.start || newInterval.end>=in.start&&newInterval.start<in.end ||
                   newInterval.start<=in.start&&newInterval.end>=in.end ||
                   newInterval.start>=in.start&&newInterval.end<=in.end) {
                    
                    // set flag to true
                    overlap = true;
                    
                    // update the newInterval
                    newInterval.start = Math.min(newInterval.start, in.start);
                    newInterval.end = Math.max(newInterval.end, in.end);
                    
                    // case where newInterval overlaps with the last interval
                    if (i==intervals.size()-1) {
                        result.add(newInterval);
                    }
                }
                // case where newInterval no longer overlaps with the current interval
                else if (overlap) {
                    result.add(newInterval);
                    result.add(in);
                    overlap = false;
                }
                // case where newInterval is non-overlapping
                // and is between the (i-1)th and ith interval
                else if (i!=0 && intervals.get(i-1).end < newInterval.start && 
                         intervals.get(i).start > newInterval.end) {
                    result.add(newInterval);
                    result.add(in);
                }
                else {
                    result.add(in);
                }
            }
            
            // special case where newInterval is non-overlapping and is the last interval
            if (newInterval.start > intervals.get(intervals.size()-1).end) {
                result.add(newInterval);
            }
            return result;
        }
    }
    

Log in to reply
 

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