(no subject)

[vdas.livejournal.com]

Мля... Совсем поломал голову. Тупая, простейшая задача, но я уже вообще ничего не соображаю. Есть список <50, <100, >=100, >200 итд итп - надо преобразовать его в пары (с-до): 1-49, 50-99, 100-200, 201-MAX

Тетки дают такие списки.
А нужны пары "С-До" .Сегодня (больше некому было) пришлось ручками это все раскладывать. [...] Тарифы, мля...[...]

Я - тупой :( Мне не приходит в голову простой и эффективный алгоритм. Все время монстры какие-то рисуютсо... Некрасивые... Хелп.

Comments

[meanab.livejournal.com]

Что-то в таком духе: два прохода. Каждый интервал представлен парой (from, to), где from и to — либо число, либо NIL. При первом проходе заполняем указанные в явном виде части интервала. При втором проходе заменяем NIL в поле from на to предыдущего интервала, а NIL в поле to — на from следующего. В реальности алгоритм будет чуть сложнее, так как нужно учитывать граничные условия и, возможно, открытость/закрытость интервала (если речь идет о целых числах, то можно просто заменять '<100' на '<=99').

[meanab.livejournal.com]

Ну, разумеется, добавить всякие проверки, на то, что при замене NIL мы не наткнемся на другой NIL, на то, что в интервале поле to должно быть больше, чем from и т.д. В этих случаях сразу signal a condition (raise an exception или как это называется в вашем языке). Можно, конечно, сделать и в один проход, но, насколько я понимаю, вопроса эффективности здесь возникать не должно, только чистоты и простоты кода.

[vdas.livejournal.com]

Язык совершенно неважен - я напишу такую задачу на абсолютно любом языке. Важен алгоритм. Простота кода необязательна. Код может быть сложен для чтения, но красив :)

[vdas.livejournal.com]

именно "в реале это будет чуть сложнее..." и интересует. Ибо совсем не "чуть сложнее".
Что в какой последовательности делать "в принципе" - и коню понятно.
А вот каков алгоритм оптимален?

Можно делать два прохода с созданием "модификаторов" для учета '<', '<=', '>', '>=' (+1, -1 итд)
Можно разложить на множества и искать пересечения (типа <100 это от -бесконечности до 99 и т.д.)
...
Вариантов много, но они громоздки и некрасивы. Задача-то не совсем экзотическая - может кому попадалась.