Leetcode: почему этот алгоритм работает медленно?

Question

Так что я пытаюсь решить эту проблему: http://oj.leetcode.com/problems/merge-intervals/

Моего решения:

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; 
} 
} 

Я видел некоторые блог, используя точно такое же решение, но получить признание, но мой отвергаются, потому что это занимает слишком много времени. Можете ли вы рассказать мне, почему это занимает больше времени, чем ожидалось? Приветствия

EDIT: решил, удалить слишком дорого, используя новый ArrayList для хранения результата быстрее

Answer 1

Первоначально вы сортируете все свои интервалы - из-за javadocs эта операция имеет сложность O (N * log (N))

Но после этого, как я заметил, вы повторяете ArrayList и иногда удаляете элементы из Это.

Но удаление какого-либо элемента из ArrayList имеет complexity O(N) (поскольку базовая реализация ArrayList - это простой массив - удаление любого элемента из середины массива требует сдвига всей правой части этого массива).

Как вы это делаете в цикле - наконец, сложность вашего альгирима будет O (N^2).

Я предлагаю вам использовать LinkedList вместо ArrayList в этом случае.

Answer 2

Вы могли бы улучшить свою сортировку с помощью одного вычисления вместо 3 сравнения:

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