Задачка из жизни

[kot_begemot]

Реально из жизни, но теперь буду спрашивать на интервью

Comments

[french_man]

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

А можно так: найти самому новый интервал, не пересекающийся с имеющимися, и добавить его в список.

Вы имеете в виду первый вариант или второй?

[kot_begemot]

Первый вариант естественно. Второй вариант тоже интересен, но, как мне кажется, тривиален - достаточно отсортировать интервалы в списке и найти два, расстояние между которыми больше 2, а если такого не найдётся, то добавить в конец.

[french_man]

Ну, если позволено сортировать по порядку, то и первый вариант тривиален.

[kot_begemot]

Ну разумеется, говорю же - задачка как раз для интервью.
Дополнительный вопрос - сколько времени займёт её запрограммировать и отладить.

[popye]

Шо, еще кто-то пишет алгоритмы? :)

[kot_begemot]

А куда деваться? Вполне себе жизненная задачка, из области оптимизации обработки параллельных потоков данных.

[popye]

Почти наверняка уже кто-то когда-то что-то такое уже написал... Осталось найти и скопировать :)

[kot_begemot]

Я боюсь, время поиска превысит время написания и отладки.
Но меня бы и такой ответ устроил (с указанием как именно и где искать).

[gingema]

А много этих интервалов вообще? Самое осмысленное - хранить их все в одном бинарном массиве. Если пустых клеток там сильно больше, чем заполненных, сделать его многомерным по принципу [блин, забыла, как эта структура данных называется, с индексами и списками по каждому индексу...] - так, чтобы, если, допустим, между 200 и 300 нет ни одной "заполненной" клетки, не держать пустые 100 клеток, а только индекс, что тут ничего нет, и место для пойнтера, на когда появится.

[kot_begemot]

Не очень тебя понял, но если ты предлагаешь тупо хранить битмап, то увы. Интервалов может быть относительно немного (скажем, десяток-другой), но они могут быть очень длинными (натурально от 0 до 10 триллионов). Столько памяти под данные отводить невозможно. А вот идея хранения дырок вместо интервалов мне нравится.

[ctapnep]

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

[kot_begemot]

Ага, всё так. Тут основной момент в том, что задачка - простая. Но находятся умельцы, пилящие её уже месяц...

[kot_begemot]

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