Подтвердить что ты не робот

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

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

У вас есть 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 Тем не менее, мне было любопытно, есть ли у более умного решения более элегантное решение.

4b9b3361

ОТВЕТЫ

Ответ 1

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

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), причем основным фактором является сортировка.

Ответ 2

Сортировка интервалов по начальной точке. Затем сверните по этому списку, объединив каждый интервал со своим соседом (т.е. (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)]

Ответ 3

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

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

Ответ 4

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

Итак, вы сначала получите:

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

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

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

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

Ответ 5

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

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)

Ответ 6

Если 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)

Ответ 7

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

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

Ответ 8

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

Я нашел поиск этой реализации.

Бретт

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

Ответ 9

int find_no_overlapping_intervals(const vector< pair<int, int>& a)
{

// a[i].first -> X ,a[i].second->Y 

// sort by start time 
sort.begin(a.begin(), a.end());


// maintain <end-time, its frequency> in m 
map<int, int> 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;
}

Ответ 10

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
    ArrayList<Interval> res = new ArrayList<Interval>();
    if (intervals == null || intervals.isEmpty())
        return res;

    Comparator<Interval> comparator = new Comparator<Interval>() {
        @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;
}

Ответ 11

Это простая реализация 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).

Ответ 12

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

#include <algorithm>
#include <iostream>
#include <set>
#include <tuple>
#include <vector>

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<Event> MakeEvents(const std::vector<Interval>& intervals)
{
    std::vector<Event> 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 <typename Less>
std::vector<std::pair<std::size_t, std::size_t>>
ComputeOverlappingIntervals(std::vector<Event>&& events, Less less)
{
    std::sort(events.begin(), events.end(), less);

    std::set<std::size_t> activeIds;
    std::vector<std::pair<std::size_t, std::size_t>> 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<Interval> 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";
    }

}

Демо

Ответ 13

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

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

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