Интервал установлен в Java

У меня есть список интервалов с целочисленными значениями [например. [1, 4], [10, 19] и т. Д.]. Есть ли способ поместить эти интервалы в контейнер некоторых коллекций Java [например. Установить] таким образом, чтобы я мог вызвать функцию 'union' для контейнера. Функция 'union' должна выдавать мне список интервалов, так что если любые 2 вставленных интервала перекрываются, то они должны быть объединены в выходных данных. Я попытался использовать класс Range в Guava, но в итоге сравнил все интервалы друг с другом перед слиянием. Элегантный подход к этому был бы по достоинству оценен! Вот что я попробовал, основываясь на ответе ниже. Выходные данные [[1, 15], [17, 20]], что правильно. Я хотел знать, есть ли какой-нибудь API, который реализует что-то вроде этого.

public static void main(String[] args) {
    // mock data
    List<MyIntRange> rng_lst = new ArrayList<Junk.MyIntRange>();
    rng_lst.add(new MyIntRange(1, 10));
    rng_lst.add(new MyIntRange(5, 15));
    rng_lst.add(new MyIntRange(17, 20));

    // sort intervals by start position
    Collections.sort(rng_lst);

    // merge the intervals which overlap
    List<MyIntRange> res_lst = new ArrayList<Junk.MyIntRange>();
    MyIntRange old_rng = null;
    for (MyIntRange cur_rng : rng_lst) {
        if (old_rng == null) {
            old_rng = cur_rng;
        } else {
            if (old_rng.rng.upperEndpoint() < cur_rng.rng.lowerEndpoint()) {
                // this does not over lap with the next one
                res_lst.add(old_rng);
                old_rng = cur_rng;
            } else {
                // overlap
                old_rng = new MyIntRange(old_rng.rng.lowerEndpoint(),
                        cur_rng.rng.upperEndpoint());
            }
        }
    }
    // add the last range
    res_lst.add(old_rng);

    // done!
    System.out.println(res_lst);
}

// wrapper around Guava's Range to make it comparable based on the
// interval's start
public static class MyIntRange implements Comparable<MyIntRange> {
    Range<Integer> rng;

    public MyIntRange(int start, int end) {
        rng = Ranges.closed(start, end);
    }

    public int compareTo(MyIntRange that) {
        int res = -1;
        if (this.rng.lowerEndpoint() > that.rng.lowerEndpoint()) {
            res = 1;
        }
        return res;
    }

    public String toString() {
        return "[" + rng.lowerEndpoint() + ", " + rng.upperEndpoint() + "]";
    }
}

Спасибо

Источник

2 ответа

Решение

Это в основном именно то, что RangeSet в только что выпущенном Guava 14.0, за исключением того, что он выполняет слияние для вас, вместо того, чтобы сообщать вам, какие диапазоны могут быть объединены.

Источник

Основной алгоритм:

  1. Сортировать интервалы по стартовому индексу
  2. Пройдите по списку. Для iая вещь:
    1. Сравните конечный индекс i с начальным индексом (i+1)ст.
    2. Если конечный индекс больше, установите конечный индекс i до конца индекса i+1и удалите i+1 элемент. (Это объединяет их.)

Сложность времени: O(nlgn)из-за первоначальной сортировки. (То есть, если удаление сделано правильно.)

Источник
Другие вопросы по тегам