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

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

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

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

предположим, что разница между начальной и конечной точками невелика, скажем [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)

Если 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), где m-число совпадений интервалы.

Я поиском нашел реализация.

Брет

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

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;
}

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;
}

Это просто 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 <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";
    }

}

демо

здесь 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 Set это сохраняет только уникальные объекты интервала.

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

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

общее время выполнения O(N lg N). Для этого требуется выходной набор размера O(N).

реализация

чтобы добавить интервалы в набор, я создал пользовательский Интервальный класс, который переопределяет 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<Interval> findIntervalsThatOverlap(List<Interval> intervals) {

    // Keeps unique intervals.
    Set<Interval> set = new HashSet<Interval>();

    // 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<Interval>(set);
}

тесты

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

public static void testcase() {

    List<Interval> intervals = null;
    List<Interval> result = null;

    intervals = new ArrayList<Interval>();

    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<Interval> intervals = null;
    List<Interval> result = null;

    intervals = new ArrayList<Interval>();

    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]

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

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

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