Leetcode: Why this algorithm is slow?

Question

So I am trying to solve this problem: http://oj.leetcode.com/problems/merge-intervals/

My solution is:

public class Solution {

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
    // Start typing your Java solution below
    // DO NOT write main() function
    // ArrayList<Interval> result = new ArrayList<Interval>();

    //First sort the intervals
    Collections.sort(intervals,new Comparator<Interval>(){
        public int compare(Interval interval1, Interval interval2) {
            if(interval1.start >  interval2.start) return 1;
            if(interval1.start == interval2.start) return 0;
            if(interval1.start <  interval2.start) return -1;
            return 42;
        }
    });

    for(int i = 0; i < intervals.size() - 1; i++){
        Interval currentInterval = intervals.get(i);
        Interval nextInterval = intervals.get(i+1);
        if(currentInterval.end >= nextInterval.start){
            intervals.set(i,new Interval(currentInterval.start,nextInterval.end));
            intervals.remove(i+1);
            i--;
        }
    }

    return intervals;   
}
}

I have seen some blogs using exactly the same solution but get accepted but mine is rejected because it takes too long. Can you enlighten me why it takes longer than expected? Cheers

EDIT: solved, remove is too costly, using a new arraylist to store the result is faster

Answer 1

Initially you are sorting all your intervals - due to javadocs, this operation has complexity O(N*log(N))

But, after that, as I have noticed - you are iterating over ArrayList, and sometimes removing elements from it.

But removing some element from ArrayList has complexity O(N) (as underlying implementation of ArrayList is plain array - removing any elemnt from the middle of array, requires shifting of the entire right part of this array).

As you do that in loop - finally, complexity of your algirithm would be O(N^2).

I'd suggest you to use LinkedList instead of ArrayList in this case.

Answer 2

You could improve your sorting by using one computation instead of 3 comparisons:

Collections.sort(intervals,new Comparator<Interval>(){
    public int compare(Interval interval1, Interval interval2) {
        return interval1.start - interval2.start;
    }
});