Clean and short Java solution with explanation


  • 5
    Y

    There are three cases with inserting an interval:

    1. the start value of the newInterval < the old interval end: insert the old interval and increment the index as we will know where this newInterval should be inserted.
    2. the start value of the old interval > newInterval end: we simply insert the old interval as there is no effect on where the newInterval should be inserted.
    3. Otherwise, we need to merge the interval, simply be getting the min of start and max of end value.

    In the end, we insert the newInterval based on the index we get on the fly.

    public class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            List<Interval> res = new ArrayList<>();
            int index = 0;
            for(int i = 0; i < intervals.size(); i++) {
                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 {
                    newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
                    newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
                }
            }
            res.add(index, newInterval);
            return res;
        }
    }

  • 0
    E

    It's better to use iterator to do the iteration instead of the accessor, because intervals.get(i) takes linear time if it is linked list. Take a look at this code: https://discuss.leetcode.com/topic/12691/short-java-code


Log in to reply
 

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