Нахождение элементарных интервалов в перекрывающихся интервалах

Question

Я наткнулся на хороший вопрос при подготовке к некоторым программным интервью.

Учитывая набор возможных перекрывающихся интервалов, вам нужно написать функцию, которая возвращает все элементарные интервалы между ними.Например: если вам заданы интервалы в виде следующего списка пар: {{1,5}, {3,10}, {5,11}, {15,18}, {16,20}}, вам нужновернуть следующее:

{{1,3}, {3,5}, {5,10}, {10,11}, {15,16}, {16,18}, {18, 20}}

Обратите внимание на следующее в приведенном выше ответе:

• В ответе отсутствует интервал {11,15}, поскольку он отсутствует во входных данных.
• Интервал {1,5} от входа был разделен на {1,3}, {3,5} в ответе из-за начальной точки "3", определенной в {3,10} ввход, который разделяет интервал на два элементарных интервала.

Подпись метода в Java:

List<Pair<Integer, Integer>> generateElementaryIntervals(List<Pair<Integer, Integer> intervals)

Одним из решений, которое я себе представлял, было разделение ввода на непересекающиесямножеств, а затем простая O (NlogN) сортировка по всем числам в каждом непересекающемся множестве даст ответ.Есть ли более эффективный способ сделать это?

Answer 1

Вы можете разбить эту проблему сначала на вложенные интервалы, а затем разбираться с каждым вложением отдельно.Под вложенностью я подразумеваю интервалы, которые разделяют хотя бы одну точку.Для приведенного вами примера:

{{1,5}, {3,10}, {5,11}, {15,18}, {16,20}}

существует две вложенности:

{1,5}, {3,10}, {5,11}

и

{15,18}, {16,20}

В общем, для определения вложений вы можете отсортироватьинтервалы, основанные на левой конечной точке (как в вашем примере), затем пробегают и запускают новое вложение всякий раз, когда вы видите {x,y}, {x',y'} с y < x'.

Для вложения формируются «элементарные интервалы»по отсортированной последовательности (без повторов) значений.В этом примере вложенности дают

(1,3,5,10,11) -> {1,3}, {3,5}, {5,10}, {10,11}

и

(15,16,18,20) -> {15,16}, {16,18}, {18,20}

Таким образом, общий алгоритм может выглядеть следующим образом:

• Сортировать интервалы на основелевая конечная точка
• Выполнять через интервалы до {x,y}, {x',y'} с y < x'
• От начала до {x,y}, составить отсортированный список конечных точек (без повторов), скажем a0,a1,...,ak
• Добавить элементарные интервалы {ai,a(i+1)} для i = 0...k-1
• Удалить интервалы до {x,y} и продолжить с шага 2

Answer 2

Вы можете отсортировать конечные точки, а затем выполнить итерацию по порядку. Чтобы узнать, входите вы или нет, вы можете сохранить количество интервалов, охватывающих каждую точку. Левый конец интервала дает +1, а правый - -1: (Обратите внимание, что я использую TreeMap , который отсортирован)

static class Pair<T, K> {
    public Pair(T first, K second){
        this.first = first;
        this.second = second;
    }

    public String toString(){
        return "(" + first + ", " + second + ")";
    }

    T first;
    K second;   
}    

static List<Pair<Integer, Integer>> generateElementaryIntervals(List<Pair<Integer, Integer>> intervals) {
    TreeMap<Integer, Integer> overlaps = new TreeMap<Integer, Integer>();
    for(Pair<Integer, Integer> interval : intervals){
        int value = overlaps.containsKey(interval.first) ? overlaps.get(interval.first)+1 : 1;
        overlaps.put(interval.first, value);

        value = overlaps.containsKey(interval.second) ? overlaps.get(interval.second)-1 : -1;
        overlaps.put(interval.second, value);
    }

    List<Pair<Integer, Integer>>  retValue = new ArrayList<Pair<Integer,Integer>>();

    int overlap = 0;
    boolean in = false;
    int last = 0;
    for(int point : overlaps.keySet()){
        if(in)
            retValue.add(new Pair(last, point));

        overlap += overlaps.get(point);
        last = point;
        in = overlap > 0;
    }

    return retValue;
}    

public static void main(String[] args) {

    List<Pair<Integer, Integer>> l = new ArrayList<Pair<Integer, Integer>>();
    l.add(new Pair<Integer, Integer>(1,5));
    l.add(new Pair<Integer, Integer>(3,10));
    l.add(new Pair<Integer, Integer>(5,11));
    l.add(new Pair<Integer, Integer>(15,18));
    l.add(new Pair<Integer, Integer>(16,20));

    for(Object o : generateElementaryIntervals(l)){
        System.out.println(o.toString());
    }

}

Answer 3

Простым алгоритмом было бы просто прочитать весь список чисел и создать элемент для каждого элемента в каждой паре.

Каждый элемент будет хранить два значения: number иявляется первым или вторым числом (из входных данных).

Эти пары будут затем отсортированы сначала по внутреннему number, а затем по его позиции (second будет идти перед first)

Чтобы распечатать список интервалов, вы должны напечатать каждое число вместе со следующим числом со следующими правилами:

• Вы не будете печатать повторяющиеся числа (например,вы не напечатали бы 5,5)
• Если у вас есть только число second, а затем число first, вы не напечатаете этот элементарный интервал, поскольку в этом диапазоне нет значений.