Вставить интервал в массив интервалов

Есть тут олимпиадник-кун, который знает какую-нибудь красивую реализацию алгоритма в один проход массива и чтобы не перебирать каждый кейс.

в job

Ваше предложение по цене.

Если у тебя, как в примере, целые числа от 1 до 10: сплющить в битмаску, орнуть, перевести обратно в интервалы. Дубово, никаких кейсов.

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

орнуть

орнул

Ты не знаешь, как разницу отрезков написать или что?

Есть n интервалов, к ним надо добавить еще один. Новый интервал вставляется без изменений

[1, 9] + [[5, 6]] => [ [1, 4], [5, 6], [7, 9] ]

Я так понимаю, что добавляемый интервал находится слева. Для этого примера не выполняется условие, так как [1, 9] не присутствует в результате. Либо ТЗ уточняй, либо примеры чини.

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

Я так полагаю, тут главная загвоздка в том, чтобы делать всё in-place, а не плодить новый массив. Это в условии не указано часом?

Потому как если новый массив делать нельзя, то вышеописанная дуристика с битовой маской отпадает однозначно, разве только для экономии памяти. Ты подумай, как ты её на интервалы разбирать-то опять будешь.

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

Я вангую, что нам неправильно дали условие.

Починил, там будет [1, 9]

В задачу не вник, но похоже на дерево отрезков.

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

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

[5, 6] + [[1, 9]] => [ [1, 4], [5, 6], [7, 9] ]
[3, 8] + [[1, 4], [5, 6], [7, 10]] => [ [1, 2], [3, 8], [9, 10] ]

Во входном массиве же отсутствие перекрытий гарантируется, или нет?

Да, гарантируется. Порядок не гарантируется и не важен в выходном массиве.

Это в условии не указано часом?

Можно массив копировать. Главное, не делать условие под каждый кейс пересечения. Так и я умею.

Ты подумай, как ты её на интервалы разбирать-то опять будешь.

Бежать вперёд по битам как же еще. Да, топорно, зато универсально, просто и надёжно.

Что за язык?

tcl

вложенные while можно заменить на пару if, но так нагляднее

Ты не знаешь, как разницу отрезков написать или что?

Могу, но в n частных случаев. А хочется в одном общем.

Насколько я понял, код не сработает для

[5, 6] + [[1, 9]] => [ [1, 4], [5, 6], [7, 9] ]

Насколько я понял, код не сработает для

код делает именно то что в описании «Есть n интервалов, к ним надо добавить еще один. Новый интервал вставляется без изменений, существующие пересекающиеся интервалы сокращаются так, чтобы не пересекаться с новым»

а вот тест-кейсы у вас не соответсвуют описанию, то да

код делает именно то что в описании

Программист, однако.

однако да :-)

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

solve (a, b) xs = (a, b) : (concat $ map (sub (b+1, a-1)) xs)
    where sub (c, d) (a, b) =
            filter (\(a, b) -> a<=b) 
                   [(min a c, min b d), (max a c, max b d)]

*Main> solve (1, 4)  [(5, 8)]
[(1,4),(5,8)]

*Main> solve (1, 6) [(5, 8)]
[(1,6),(7,8)]

*Main> solve (6, 9) [(5, 8)]
[(6,9),(5,5)]

*Main> solve (5, 6) [(1, 9)] 
[(5,6),(1,4),(7,9)]

*Main> solve (1, 9)  [(5, 6)]
[(1,9)]

*Main> solve (3, 8) [(1, 4), (5, 6), (7, 10)] 
[(3,8),(1,2),(9,10)]

Где мои деньги?

двоичный поиск делением пополам

который знает какую-нибудь красивую реализацию алгоритма в один проход

А тут как-то вообще можно сделать не в один проход? Тупейшая задача со скучнейшим решением. С сынишкой контрольную по информатике делаете?

Где мои деньги?

их с тебя надо взять по тз

их с тебя надо взять по тз

Есть тут олимпиадник-кун

это платная олимпиада

Получи лайк за Tcl ^_^

Где мои деньги?

Где обычно. В кармене/кошельке, наверное. А это что за язык?

С сынишкой контрольную по информатике делаете?

В пятницу могз засох. Я не был уверен, что тестовых кейсов всего 6.

Тупейшая задача со скучнейшим решением.

Так нужно же не скучное, типа битовой маски.

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

А это что за язык?

Это haskell.

Входные интервалы не пересекаются.

А в примерах как раз пересечения есть.

Где?

Тред элитных языков. Ерланга еще не хватает.

[1, 6] + [[5, 8]]

5 и 6 - пересечение интервалов.

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

Так нужно же не скучное, типа битовой маски.

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

Порядок интервалов в массиве не важен на выходе и не установлен на входе.

Тогда видимо за линейное время не выйдет. Если интервалы отсортированы, то есть простой линейный алгоритм.

Да. [1, 6] - входной, который надо добавить, [[5, 8]] - исходные.

Это если они нужны, но аноним, похоже, прав и всё делается за один проход несколькими проверками

Главный вопрос был в том, сколькими именно и точно ли я всех их учёл или нет. Но т.к. ресурсы мозга были ограничены в ход пошел план Б: спросить на ЛОРе как сделать без обхода. В принципе походу треда я придумал, что можно просто ничего не делать - если точку проверять вхождение последовательно проходя все интервалы, то можно просто добавить новый интервал в начало.

Дай угадаю. Задача зелёная.

Тогда видимо за линейное время не выйдет. Если интервалы отсортированы, то есть простой линейный алгоритм.

Но выше висит программа, которая за линейное время делает. Зачем там сортировать что-то?

Чёт как-то просто для олимпиадной задачи. Или есть какой-то подвох?
Так вроде всё тупо в лоб делается:
Новый интервал просто вставляется в массив.
И цикл по всем остальным интервалам в массиве:
1. Если интервал пересекается с новым, тогда он укорачивается, чтобы не пересекаться
2. Если новый интервал оказывается внутри текущего, тогда текущий разрывается на 2
Это ровно то, что написано в условии, остаются ещё два варианта:
3. Если текущий интервал оказывается внутри нового - то он уничтожается
4. Если текущий интервал полностью левее или правее нового - тогда остаётся без изменений.

1. Если интервал пересекается с новым, тогда он укорачивается, чтобы не пересекаться
2. Если новый интервал оказывается внутри текущего, тогда текущий разрывается на 2 Это ровно то, что написано в условии, остаются ещё два варианта:
3. Если текущий интервал оказывается внутри нового - то он уничтожается
4. Если текущий интервал полностью левее или правее нового - тогда остаётся без изменений.

Там даже такой перебор вариантов не нужен. Все эти if-then-else уже вписаны в min() и max() :)

Или есть какой-то подвох?

Не должно быть, но мало ли.

Дай угадаю. Задача зелёная.

Что значит зелёная?

https://assets.leetcode.com/users/alementuev/image_1573422238.png посмотри на одну из колонок справа

затруднение только в несимметричности ( т/е если интервал из набора польностю покрыт новым(вставляемым) интервалом тогда новый давит - если же вставляемый покрыт уже имеющимся в наборе то имеющийся рвётся вставляемым) крч

далее везде A<=B и x<=y

  Пусть [A,B] - добавляемый в набор -

  для  каждого интервала [x,y]  из входного набора

      ((y<A)или(B<x)&&push(x,y)

      ||push(x,A-1)&&push(B+1,y)  

  push(A,B)

где push(q,p) is (q<=p)&&ДобавитьВвыходнойНабор([q,p]);return TRUE

т.е возможно 3 различных случая нового и очередного из набора:

1. интервалы удаленны друг от друга тогда вход на выход
2. перекрытие тогда на выход лишь та(те) часть входа что за пределами нового