LINUX.ORG.RU

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

 ,


0

2

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

[1, 4] + [[5, 8]] => [ [1, 4], [5, 8] ]
[1, 6] + [[5, 8]] => [ [1, 6], [7, 8] ]
[6, 9] + [[5, 8]] => [ [5, 5], [6, 9] ]
[5, 6] + [[1, 9]] => [ [1, 4], [5, 6], [7, 9] ]
[1, 9] + [[5, 6]] => [ [1, 9] ]
[3, 8] + [[1, 4], [5, 6], [7, 10]] => [ [1, 2], [3, 8], [9, 10] ]
Порядок интервалов в массиве не важен на выходе и не установлен на входе. Входные интервалы не пересекаются.
Есть тут олимпиадник-кун, который знает какую-нибудь красивую реализацию алгоритма в один проход массива и чтобы не перебирать каждый кейс.

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

★★★★★

Последнее исправление: crutch_master (всего исправлений: 7)

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

в job

anonymous
()

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

t184256 ★★★★★
()
Ответ на: комментарий от t184256

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

crutch_master ★★★★★
() автор топика
Последнее исправление: crutch_master (всего исправлений: 1)

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

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

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

dsxl
()

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

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

Waterlaz ★★★★★
()
proc add_interval { intervals from to } {
  set result {}
  foreach { a b } $intervals {
    while { $a >= $from && $a<=$to } {
      incr a
    }
    while { $b >= $from && $b<=$to } {
      incr b -1
    }
    if { $a < $b } {
       lappend result $a
       lappend result $b
    }
  }
  lappend result $from
  lappend result $to
}

MKuznetsov ★★★★★
()

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

Tanger ★★★★★
()
Ответ на: комментарий от anonymous

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

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

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

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

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

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

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

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

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

crutch_master ★★★★★
() автор топика
Ответ на: комментарий от anonymous

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

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

crutch_master ★★★★★
() автор топика
Ответ на: комментарий от crutch_master

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

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

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

MKuznetsov ★★★★★
()
Ответ на: комментарий от crutch_master

однако да :-)

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

MKuznetsov ★★★★★
()
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)]

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

Waterlaz ★★★★★
()
Последнее исправление: Waterlaz (всего исправлений: 1)

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

Legioner ★★★★★
()

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

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

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

crutch_master ★★★★★
() автор топика

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

crutch_master ★★★★★
() автор топика
Ответ на: комментарий от Waterlaz

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

crutch_master ★★★★★
() автор топика
Ответ на: комментарий от xmikex

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

xaizek ★★★★★
()
Ответ на: комментарий от crutch_master

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

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

xaizek ★★★★★
()
Последнее исправление: xaizek (всего исправлений: 1)

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

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

X512 ★★★★★
()
Ответ на: комментарий от xmikex

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

crutch_master ★★★★★
() автор топика
Ответ на: комментарий от xaizek

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

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

crutch_master ★★★★★
() автор топика
Ответ на: комментарий от X512

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

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

Waterlaz ★★★★★
()

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

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

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

Waterlaz ★★★★★
()
Ответ на: комментарий от anonymous

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

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

crutch_master ★★★★★
() автор топика
4 апреля 2022 г.

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

далее везде 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. перекрытие тогда на выход лишь та(те) часть входа что за пределами нового
qulinxao3
()
Последнее исправление: qulinxao3 (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.