Java solution, no extra space


  • 0
    S
    //Sorting takes O(n log(n)) and merging the intervals takes O(n). So, the resulting algorithm takes O(n log(n)).
    public List<Interval> merge(List<Interval> intervals) {
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval i1, Interval i2) {
                return Integer.compare(i1.start, i2.start);
            }
        });
        
        int i = 1;
    
        while (i < intervals.size()){
            Interval l1 = intervals.get(i-1);
            Interval l2 = intervals.get(i);
            if(l2.start > l1.end) i++;
            else {
                intervals.remove(l1);
                intervals.remove(l2);
                intervals.add(i-1, new Interval(l1.start, Math.max(l1.end, l2.end)));
            }
        }
        
        return intervals;
    }

Log in to reply
 

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