Я знаю, что это хорошо определенная проблема, которая обычно решается с помощью интервальных деревьев. Я нашел решение здесь . Но у меня все еще есть некоторые вопросы по этому поводу.
Метод I: Используя деревья интервалов, сложность времени O (logN + K), где N - общее количество интервалов, а K - количество перекрывающихся интервалов.
(1) Как мы выбираем центральные точки? Wiki на самом деле не упоминал варианты, и в этой ссылке упоминается "Значения разбиения в этом дереве также основаны на медианах, но медианные значения берутся из конечных точек 2N всех интервалы. ". Насколько я понимаю, мы выбираем центральные точки, чтобы сделать дерево интервалов «сбалансированным». Но если это так, значит ли это, что деревья интервалов не могут быть самоуравновешенными (потому что это зависит от выбора центральных точек)?
Метод II: Построить хэш-карту. Временная сложность O (1)
Мне кажется, этот метод использует интервалы пересечения в качестве ключа, а список интервалов, соответствующих этому пересечению, - в качестве значения. Например, при заданных интервалах [1, 3] и [2, 4] ключи для карты хеша будут [1,2], [2,3], [3,4], а значения будут [1, 2 ] => {[1,3]}, [2,3] => {[1,3], [2,4]}, [3,4] => {[2,4]}.
Мои вопросы
(1) В приведенном выше примере, что если мы запросим число = 2, то есть два интервала пересечения, содержащие 2, как мы узнаем, чье значение вернуть?
(2) Если один из интервалов пересечения подобен [2,2], следует ли нам использовать его в качестве отдельного ключа? Мне было трудно проанализировать два случая. Во-первых, пересечение имеет начало = конец, во-вторых, что входные интервалы содержат два одинаковых интервала, например, [1,2] и [1, 2]
Буду признателен за любую помощь!
При необходимости ниже приведен мой код для решения 2
Map<Interval, List<Interval>> map;
private void init(List<Interval> input) {
// step 1 sort input
// step 2:
PriorityQueue<Interval> minHeap = new PriorityQueue<>(new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.end - o2.end;
}
});
Map<Interval, List<Interval>> map = new HashMap<>();
int start = 0; // init should be redundant
for (int i = 0; i < input.size(); i++) {
Interval cur = input.get(i);
if (minHeap.isEmpty()) {
start = input.get(i).start;
minHeap.offer(cur);
} else if (minHeap.peek().end < cur.start) { // [] both start and end are inclusive
List<Interval> values = new ArrayList<>(minHeap);
Interval min = minHeap.poll();
map.put(new Interval(start, min.end), values);
i--;
start = min.end;
} else {
minHeap.offer(cur);
map.put(new Interval(start, cur.start), new ArrayList<>(minHeap));
start = cur.start;
}
}
// pop until the pq is empty
while (!minHeap.isEmpty()) {
List<Interval> values = new ArrayList<>(minHeap);
Interval cur = minHeap.poll();
map.put(new Interval(start, cur.end), values);
}
this.map = map;
}