Возможный вопрос для интервью: как найти все перекрывающиеся интервалы

Это не вопрос интервью как таковой , поскольку я натолкнулся на это в своем проекте, но я подумал, что это может быть достойный спорный вопрос.

У вас есть N пар интервалов, скажем целых чисел. Вам необходимо указать все интервалы, которые перекрываются друг с другом в O (N) времени. Например, если у вас есть

{1, 3} {12, 14} {2, 4} {13, 15} {5, 10}

ответ {1, 3}, {12, 14}, {2, 4}, {13, 15}. Обратите внимание, что вам не нужно группировать их, поэтому результат может быть в любом порядке, как в примере.

Я просто бросил время O (N), потому что алгоритм KMP берет O (N) для поиска строк. : D

Лучшее, что я придумал и что я сейчас использую в проекте, – O (N ^ 2). Да, грубая сила довольно грустная, но никто не жалуется, поэтому я не буду реорганизовать ее. : P Тем не менее, мне было любопытно, есть ли у более умного решения более элегантное решение.

Выбросьте конечные точки интервалов в массив, обозначив их как начальные или конечные точки. Отсортируйте их, разбив галстуки, разместив конечные точки перед стартовыми точками, если интервалы закрыты, или наоборот, если они полуоткрыты.

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E 

Затем перебирайте список, отслеживая, сколько интервалов мы находимся (это соответствует количеству обрабатываемых начальных точек минус количество конечных точек). Всякий раз, когда мы нажимаем начальную точку, пока мы уже находимся в промежутке, это означает, что мы должны иметь перекрывающиеся интервалы.

 1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E ^ ^ overlap overlap 

Мы можем найти, какие интервалы перекрываются с ними, сохраняя данные вместе с конечными точками и отслеживая, с какими интервалами мы находимся.

Это решение O (N logN), причем основным фактором является сортировка.

Сортируйте интервалы по начальной точке. Затем сверните этот список, объединив каждый интервал со своим соседом (т.е. (1,4), (2,6) -> (1,6)), если они перекрываются. Полученный список содержит те интервалы, которые не имеют совпадающего партнера. Отфильтруйте их из исходного списка.

Это линейно по времени после первоначальной операции сортировки, которая может быть выполнена с любым алгоритмом (n log n). Не уверен, как вы обойдете это. Даже операция «отфильтровать дубликаты» в конце является линейной, если вы воспользуетесь уже отсортированным порядком ввода и вывода первой операции.

Вот реализация в Haskell:

 -- Given a list of intervals, select those which overlap with at least one other inteval in the set. import Data.List type Interval = (Integer, Integer) overlap (a1,b1)(a2,b2) | b1 < a2 = False | b2 < a1 = False | otherwise = True mergeIntervals (a1,b1)(a2,b2) = (min a1 a2, max b1 b2) sortIntervals::[Interval]->[Interval] sortIntervals = sortBy (\(a1,b1)(a2,b2)->(compare a1 a2)) sortedDifference::[Interval]->[Interval]->[Interval] sortedDifference [] _ = [] sortedDifference x [] = x sortedDifference (x:xs)(y:ys) | x == y = sortedDifference xs ys | x < y = x:(sortedDifference xs (y:ys)) | y < x = sortedDifference (x:xs) ys groupIntervals::[Interval]->[Interval] groupIntervals = foldr couldCombine [] where couldCombine next [] = [next] couldCombine next (x:xs) | overlap next x = (mergeIntervals x next):xs | otherwise = next:x:xs findOverlapped::[Interval]->[Interval] findOverlapped intervals = sortedDifference sorted (groupIntervals sorted) where sorted = sortIntervals intervals sample = [(1,3),(12,14),(2,4),(13,15),(5,10)] 

Стандартный подход для задач «интервалы в очереди» – сортировать их по начальной точке, а затем просто идти от первого до последнего. O(n*logn) ( O(n) если он уже отсортирован)

 end = 0; for (current in intervals) { if current.start < end { // there's an intersection! // 'current' intersects with some interval before it ... } end = max(end, current.end) } 

Не уверен относительно O (N), но что, если мы сначала отсортируем их по первому числу в каждом кортеже, а затем последовательно найдем те, где первое число кортежа больше, чем у наибольшего числа, наблюдаемого в предыдущих кортежах, что также делает не накладываться на следующий кортеж.

Таким образом, вы сначала получите:

{1, 3}, {2,4}, {5, 10}, {12, 14}, {13, 15}

так как 4 (наибольший) <5 и 10 <12, {5, 10} изолированы.

Это приведет к тому, что мы будем отслеживать наибольшее число, с которым мы сталкиваемся, и каждый раз, когда мы находим кортеж, начальное число которого больше, мы проверяем, совпадает ли оно со следующим.

Это становится зависимым от эффективности алгоритма сортировки, потому что последним процессом будет O (N)

Предположим, что разница между начальным и конечным точками мала, скажем <32. напр. 1..32. Затем каждый интервал может быть записан как битовый шаблон в 32-битном слове. например [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 . Два интервала или комбинации интервалов перекрываются, если их побитовое AND отличное от нуля. например. [1,2] перекрывает [1,3] потому что 001&011 == 001 , отличное от нуля. O (n) alg должен поддерживать работу побитового ИЛИ интервалов, видимых до сих пор, и каждый новый:

 bitsSoFar = 0 for (n=0; n < bitPatterns.length; n++) if (bitPatterns[n] & bitsSoFar != 0) // overlap of bitPatterns[n] with an earlier pattern bitsSoFar |= bitPatterns[n] 

Оставленный как упражнение:

  • модифицировать алгоритм, чтобы также идентифицировать перекрытие битового шаблона с более поздним

  • выработать битовый шаблон для интервала в O (1)

Если N пар интервалов – целые числа, то мы можем получить их в O (n).

Сортируйте его по первому числу в паре, затем по второму числу. Если все являются целыми числами, мы можем использовать сортировку ковша или сортировку радиуса, чтобы получить ее с помощью O (n).

{1, 3}, {2,4}, {5, 10}, {12, 14}, {13, 15}

Затем объедините один за другим,

{1,3}

{1,4} с перекрытием {1,3} и {2,4}

{1,4}, {5,10}

{1,4}, {5,10}, {12,14}

{1,4}, {5,10}, {12,15} с перекрытием {12,14} и {13,15}

Комбинация займет время O (N)

Эта проблема может быть сведена к проблеме единственности элемента.

Уникальность элемента имеет нижнюю границу Omega (n log n) (подсчет количества сравнений), поэтому вы не можете сделать лучше этого.

Прошло довольно много времени с тех пор, как я использовал его, но решение, которое я использовал, было производным от красно-черного дерева, описанного во Введении к Алгоритмам, называемому интервальным деревом. Это дерево, отсортированное по интервалу запуска, поэтому вы можете быстро (двоичный поиск) сначала получить первый подходящий узел. IIRC, узлы были упорядочены по свойству, что позволяет вам «ходить» по дереву, когда узлы-кандидаты не могут соответствовать вашему интервалу. Поэтому я думаю, что это O (m) search, где m – количество совпадающих интервалов.

Я искал эту реализацию .

Brett

Перечитывая вопрос, это не то, что вы просили. Я думаю, что это лучшая реализация, когда у вас есть список (например) встреч, уже запланированных в конференц-залах (которые добавляются к дереву), и вы хотите найти, какие комнаты по-прежнему доступны для встречи с новым стартом и продолжительностью (поисковый запрос). Надеюсь, это решение имеет некоторое значение.

 int find_no_overlapping_intervals(const vector< pair& a) { // a[i].first -> X ,a[i].second->Y // sort by start time sort.begin(a.begin(), a.end()); // maintain  in m map m; // i // for each point, we know its a[i].X >= a[0].X. ....a[i-1].X // there will be overlap, if for some j < i, a[j].Y >= a[i].X // lower_bound to find this.. it can be found in O(log(n)) as we use std::map for maintaining y int ans = 0; for (int i=0; i < a.begin(); i++) { auto sit = m.lower_bound(m.begin(), m.end(), a[i].first); auto eit = m.upper_bound(m.begin(), m.end(), a[i].first); for (auto it = sit; it != eit; it++) ans += it->second; m[a[i].second]++; } return ans; } 
 public ArrayList merge(ArrayList intervals) { ArrayList res = new ArrayList(); if (intervals == null || intervals.isEmpty()) return res; Comparator comparator = new Comparator() { @Override public int compare(Interval i1, Interval i2) { if (i1.start < i2.start) return -1; else if (i1.start > i2.start) return 1; else { if (i1.end < i2.end) return -1; else if (i1.end > i2.end) return 1; else return 0; } } }; Collections.sort(intervals, comparator); for (int i = 0; i < intervals.size(); i++) { Interval cur = intervals.get(i); if (res.isEmpty()) { res.add(cur); } else { Interval last = res.get(res.size() - 1); if (last.end >= cur.start) { last.end = Math.max(last.end, cur.end); } else { res.add(cur); } } } return res; } 

Это простая реализация O(N*log(N)) в Python:

 def overlapping(intervals): last = (-1, -1) overlapping = set() for curr in sorted(intervals, key=lambda p: p[0]): if curr[0] < last[1]: overlapping.add(curr) overlapping.add(last) last = max(curr, last, key=lambda p: p[1]) return list(overlapping - set((-1, -1))) print overlapping([(1, 3), (12, 14), (2, 4), (13, 15), (5, 10)]) #=> [(1, 3), (13, 15), (2, 4), (12, 14)] 

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

Сортировочная часть – это та, которая требует наибольшего времени, поэтому конечная сложность – N*log(N) .

Реализация на C ++ с использованием алгоритма развертки ( O(N log N) ):

 #include  #include  #include  #include  #include  struct Interval { double start; double end; }; //----------------------------------------------------------------------------- // Enum to qualify event: Start/End of "segment-line" enum class EIntervalState { Start, End }; //----------------------------------------------------------------------------- // Events used for collision detection struct Event { double pos; EIntervalState state; std::size_t id; }; //----------------------------------------------------------------------------- // Comparator to use if {1, 2} and {2, 3} should overlap class LessIncludeLimit { public: bool operator()(const Event& lhs, const Event& rhs) const { return std::tie(lhs.pos, lhs.state) < std::tie(rhs.pos, rhs.state); } }; //----------------------------------------------------------------------------- // Comparator to use if {1, 2} and {2, 3} should not overlap class LessExcludeLimit { public: bool operator()(const Event& lhs, const Event& rhs) const { return std::tie(lhs.pos, rhs.state) < std::tie(rhs.pos, lhs.state); } }; //----------------------------------------------------------------------------- std::vector MakeEvents(const std::vector& intervals) { std::vector res; std::size_t id = 0; for (const auto& interval : intervals) { res.push_back({interval.start, EIntervalState::Start, id}); res.push_back({interval.end, EIntervalState::End, id}); ++id; } return res; } //----------------------------------------------------------------------------- template  std::vector> ComputeOverlappingIntervals(std::vector&& events, Less less) { std::sort(events.begin(), events.end(), less); std::set activeIds; std::vector> res; for (const auto& event : events) { switch (event.state) { case EIntervalState::Start: { for (const auto& id : activeIds) { res.emplace_back(std::minmax(event.id, id)); } activeIds.emplace(event.id); break; } case EIntervalState::End: { activeIds.erase(event.id); break; } } } return res; } 

И используйте его:

 int main() { const std::vector intervals = { {1, 3}, {12, 14}, {2, 4}, {13, 15}, {5, 10} }; for (const auto& p : ComputeOverlappingIntervals(MakeEvents(intervals), LessExcludeLimit{})) { std::cout << "intervals " << p.first << " and " << p.second << " overlap\n"; } } 

демонстрация

Вот реализация O(N lg N) в Java, которая расширяет ответ, предоставленный @Nikita Rybak.

Мое решение находит каждый интервал, который перекрывается по крайней мере с одним другим интервалом и считает их как перекрывающимися интервалами. Например, два интервала (1, 3) и (2, 4) из исходного вопроса OP перекрываются друг с другом, и поэтому в этом случае имеется 2 перекрывающих друг друга интервала. Другими словами, если интервал A перекрывается с интервалом B, я добавляю как A, так и B к результирующему набору интервалов, которые перекрываются.

Теперь рассмотрим интервалы (1, 100) , (10, 20) и (30, 50) . Мой код найдет, что:

 [ 10, 20] overlaps with [ 1, 100] [ 30, 50] overlaps with [ 1, 100] Resulting intervals that overlap with at least one other interval: [ 1, 100] [ 30, 50] [ 10, 20] 

Чтобы предотвратить (1, 100) от подсчета дважды, я использую набор Java, который хранит только уникальные объекты Interval.

Мое решение следует этой схеме.

  1. Сортировка всех интервалов по начальной точке. Этот шаг равен O(N lg N) .
  2. Следите за intervalWithLatestEnd , интервал с последней конечной точкой.
  3. Итерация по всем интервалам в отсортированном списке. Если интервал перекрывается с intervalWithLatestEnd , добавьте оба значения в Set. intervalWithLatestEnd обновленияWithLatestEnd при необходимости. Этот шаг равен O(N) .
  4. Верните Set (и при необходимости конвертируйте в список).

Общее время работы – O(N lg N) . Он требует выходного набора размера O(N) .

Реализация

Чтобы добавить интервалы в набор, я создал собственный class Interval, который переопределяет equals() , как и ожидалось.

 class Interval { int start; int end; Interval(int s, int e) { start = s; end = e; } @Override public String toString() { return String.format("[%3d, %3d]", start, end); } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + start; result = prime * result + end; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; final Interval other = (Interval) obj; if (start != other.start) return false; if (end != other.end) return false; return true; } } 

И вот код, который выполняет алгоритм:

 private static List findIntervalsThatOverlap(List intervals) { // Keeps unique intervals. Set set = new HashSet(); // Sort the intervals by starting time. Collections.sort(intervals, (x, y) -> Integer.compare(x.start, y.start)); // Keep track of the interval that has the latest end time. Interval intervalWithLatestEnd = null; for (Interval interval : intervals) { if (intervalWithLatestEnd != null && interval.start < intervalWithLatestEnd.end) { // Overlap occurred. // Add the current interval and the interval it overlapped with. set.add(interval); set.add(intervalWithLatestEnd); System.out.println(interval + " overlaps with " + intervalWithLatestEnd); } // Update the interval with latest end. if (intervalWithLatestEnd == null || intervalWithLatestEnd.end < interval.end) { intervalWithLatestEnd = interval; } } // Convert the Set to a List. return new ArrayList(set); } 

Испытательные случаи

Вот пример, который запускает исходные интервалы OP:

 public static void testcase() { List intervals = null; List result = null; intervals = new ArrayList(); intervals.add(new Interval(1, 3)); intervals.add(new Interval(12, 14)); intervals.add(new Interval(2, 4)); intervals.add(new Interval(13, 15)); intervals.add(new Interval(5, 10)); result = findIntervalsThatOverlap(intervals); System.out.println("Intervals that overlap with at least one other interval:"); for (Interval interval : result) { System.out.println(interval); } } 

с результатом:

 [ 2, 4] overlaps with [ 1, 3] [ 13, 15] overlaps with [ 12, 14] Intervals that overlap with at least one other interval: [ 2, 4] [ 1, 3] [ 13, 15] [ 12, 14] 

Наконец, вот более сложный тестовый пример:

 public static void testcase() { List intervals = null; List result = null; intervals = new ArrayList(); intervals.add(new Interval(1, 4)); intervals.add(new Interval(2, 3)); intervals.add(new Interval(5, 7)); intervals.add(new Interval(10, 20)); intervals.add(new Interval(15, 22)); intervals.add(new Interval(9, 11)); intervals.add(new Interval(8, 25)); intervals.add(new Interval(50, 100)); intervals.add(new Interval(60, 70)); intervals.add(new Interval(80, 90)); result = findIntervalsThatOverlap(intervals); System.out.println("Intervals that overlap with at least one other interval:"); for (Interval interval : result) { System.out.println(interval); } } 

с результатом:

 [ 2, 3] overlaps with [ 1, 4] [ 9, 11] overlaps with [ 8, 25] [ 10, 20] overlaps with [ 8, 25] [ 15, 22] overlaps with [ 8, 25] [ 60, 70] overlaps with [ 50, 100] [ 80, 90] overlaps with [ 50, 100] Intervals that overlap with at least one other interval: [ 2, 3] [ 8, 25] [ 9, 11] [ 50, 100] [ 1, 4] [ 15, 22] [ 10, 20] [ 60, 70] [ 80, 90] 

Вы можете перечислить список один раз и сохранить хеш-таблицу всех интервалов, встречающихся до сих пор. Если интервал ввода является частью некоторого интервала из hash-таблицы, объедините его в hash-таблицу. Отметьте не-примитивные интервалы (объединенные интервалы, которые состоят из нескольких интервалов).

Затем вы переходите через список во второй раз и для каждого интервала проверяете hash-таблицу, содержится ли она в объединенном интервале или нет.

Я не знаю, является ли это O (N), но это намного лучше, чем O (N ^ 2).

  • Количество отсчетов 1 в двоичном представлении
  • Как найти номер в массиве 2d, отсортированном слева направо и сверху вниз?
  • Что такое циклический инвариант?
  • синусоидальной волны, которая медленно увеличивает частоту от f1 до f2 в течение заданного времени
  • Объединить данные гироскопа и акселерометра
  • Существует ли алгоритм сортировки по целому числу O (n)?
  • Динамическое программирование и замещение: подходы снизу вверх и сверху вниз
  • Найти кратчайший путь в графе, который посещает определенные узлы
  • O (klogk) для нахождения k-го наименьшего элемента из двоичной кучи
  • Найти цикл кратчайшей в ориентированном графе с положительными весами
  • Какой самый быстрый алгоритм сортировки связанного списка?
  • Interesting Posts
    Давайте будем гением компьютера.