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

Question

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

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

Answer 1

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

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

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