Объединение пересекающихся интервалов

Возможный дубликат:
объединение интервалов
как эффективно перекрывать интервалы

Учитывая список интервалов, в которых указаны все целые числа, должна быть возможность свернуть их в один интервал, если они действительно пересекаются или перекрываются, в противном случае данные интервалы остаются неизменными. Скажем, если вход, например, I [(2-6), (1-4), (8-12)], ожидаемый результат будет [(1-6), (8-12)], например. II [(4-7), (2-6), (1-4), (8-12), (7-9)] ожидаемый результат [(1-12)].

Исправление: пропущена часть сортировки, так что да, это время O (nlogn), а НЕ O (n). Спасибо что подметил это. Я написал и протестировал подход с алгоритмом времени O (nlogn) и пространством O (2n), который работает. Поделитесь кодом этого подхода ниже. Мне интересно услышать разные подходы к решению этой проблемы, возможно, более эффективные.

// Предполагая, что каждый из интервалов (2-6) и т. Д. Представлены как объекты «Интервал» (определение класса показано ниже), где low = 2 и high = 6 // Шаг 1: Сортировка по нижней конечной точке данного интервалы // Шаг 2: найти объединение отсортированных интервалов

//Вход:

List<Interval> intervalList = new ArrayList<Interval>(); 

//Выход:

List<Interval> unionList = new ArrayList<Interval>();    

private static final Comparator<Interval> Low_EPSorter = new LowEPSorter();

class Interval {
  int low, high;

  Interval(int l, int h, int m) {
    low = l;
    high = h;
  }
}

//// ------- BEGIN: метод, который находит объединение заданных интервалов ---- //////

void UnionOfIntervals() {
  //Find intersection and combine intervals as necessary
  int sz = intervalList.size();

  // sort by low endpoint
  Collections.sort(intervalList, Low_EPSorter);

      for(int i = 0; i < sz; i++) {
        int j = i;
        if(j > 0) {
          if( Intervals.intersect(intervalList.get(j), intervalList.get(j-1)) ) {
            Interval v = union(intervalList.get(j), intervalList.get(j-1));
            checkAndAdd(v, unionList);
          }
          else {
            if(i == 1) {
              unionList.add(intervalList.get(j-1));
              unionList.add(intervalList.get(j));
          }
          else {
            unionList.add(intervalList.get(j));
          }
        } //No intersection
      } //If 2 elements atleast
      }

      //Print intervals after union
      System.out.println("Input intervals after sorting:");
      for(Interval v : intervalList) {
        System.out.print(v.low + "," + v.high + " ");
      }
      System.out.println();
      System.out.println("Union of intervals:");
      for(Interval v : unionList) {
        System.out.print(v.low + "," + v.high + " ");
      }
    }

    void checkAndAdd(Interval x, List t) {
      int top = t.size()-1;
      if( top >=0 && Intervals.intersect(unionList.get(top), x) ) {
        Interval v = union(unionList.get(top), x);
        t.remove(top);
        t.add(v);
      }
      else {
        t.add(x);
      }
    }

//// ------- END: Метод, который находит объединение заданных интервалов ---- //////

//// --- вспомогательные методы --- ////

static boolean intersect(Interval a, Interval b) {
      boolean r = false;
      if(b.high < a.low || b.low > a.high)
        r = false;
      else if(a.low <= b.high && b.low <= a.high)
        r = true;
      return r;
}

Interval union(Interval a, Interval b) {
      int l = (a.low < b.low) ? a.low : b.low;
      int max = (a.high > b.high) ? a.high : b.high;
      return new Interval(l, max);
}

private static class LowEPSorter implements Comparator<Interval> {

      public int compare(Interval a, Interval b) {
        int r = 0;
        if(a.low < b.low)
          r = -1;
        else if(a.low > b.low)
          r = 1;
        return r;
      }

}