Java solution with comments (revised based on problem 56. Merge intervals)


  • 0

    I did "Merge Intervals" problem first. When I came to this problem, I realized that I only need to insert the new interval in the list of intervals, and call the function "merge" that I wrote in "Merge Intervals".
    Not sure if this would be a good answer, but if you have done Merge Intervals, I guess you should be able to get this solution very naturally. Hope this could help:)

    /**
     * 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) {
            intervals.add(newInterval);
            return merge(intervals);
        }
        public List<Interval> merge(List<Interval> intervals) {
            //1. sort the intervals by their starting points 
            //2. take the first interval and compare its end with the next interval starts: 
            //2a. if they overlap, update the end to be the max end of the overlapping intervals 
            //2b. if they don't overlap, add the previous "extended interval 
            if (intervals.size() <= 1) return intervals;  
            Collections.sort(intervals, new Comparator<Interval>() {
                public int compare(Interval i1, Interval i2) {
                    return (i1.start - i2.start); 
                }
            }); 
            
            List<Interval> res = new ArrayList<>(); 
            int start = intervals.get(0).start; 
            int end = intervals.get(0).end; 
            for (Interval curr : intervals) {
                if (curr.start > end) { //no overlap //add
                    res.add(new Interval(start, end));  
                    start = curr.start; 
                    end = curr.end; 
                } else {//overlap //merge 
                    end = Math.max(end, curr.end);
                }
            }
            res.add(new Interval(start, end)); 
            return res; 
        }
    }
    

Log in to reply
 

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