Java solution, no extra space

  • 0
    //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>() {
            public int compare(Interval i1, Interval i2) {
                return, 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.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.