(no subject)

[vdas.livejournal.com]

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

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

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

Comments

[a-bronx.livejournal.com]

Всё в целых числах?

Сортируем список и начинаем создавать интервалы. Все интервалы - полуоткрытые. Первый интервал - [1, null). Бежим по списку. Каждый шаг закрывает один интервал и создаёт новый.
- Если встречаем "<N" - текущий интервал закрывается числом N-1, и открываем новый интервал [N, null).
- Если "<=N" - число N закрывает текущий интервал, создаём новый интервал [N+1, null).
- Если ">=N" - число N-1 закрывает текущий интервал, создаём [N, null).
- Если ">N" - число N закрывает текущий интервал, создаём [N+1, null).
По окончании закрываем последний интервал числом MAX.

[a-bronx.livejournal.com]

Да, сортировать список нужно по-хитрому:

"<=N" == ">N" == "<N+1" == ">=N+1" < "<=N+1" == ">N+1" == ...

Вообще говоря, эквивалентных элементов в списке быть не должно, т.к. они сгенерят одинаковые интервалы, а это исключительная ситуация.

[vdas.livejournal.com]

не только в целых, но это не суть - вопрос реализации :)
дело вот в чем:
<100
>150

создадутся:
1-99
100-150 - этого интервала нет. ошибка.
150-max


<=100
>=100
неверно создадутся. неоднозначность. ошибка.

Проблема скорее в реализации "защиты от дурака" - заполнить интревалы и отметить ошибки.

[a-bronx.livejournal.com]

А, если допускаются разрывы, то их можно поймать во время генерации интервалов по типичным паттернам в последовательности, например, отлавливать смежные пары ("<", ">") и т.п. Простой автомат с запоминанием предыдущего шага.

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

[a-bronx.livejournal.com]

Тьфу, на свежую голову вижу косяк: я сначала написал, что все интервалы полуоткрытые, а на деле генерирую закрытые. Ну да фигня, в общем-то, чуть упростятся выражения при генерации (и чуть усложнятся при выводе):

"<N", ">=N" ==> [_, N), [N, null)
"<=N", ">N" ==> [_, N+1), [N+1, null)

[vdas.livejournal.com]

спасибо - я уже вроде как оклемался немного - завтра займусь :)