Доброго времени суток. Стоит задача расположить отрезки на временной оси без пересечений.

В строках ТЗ находятся эти самые отрезки, каждая строка - отрезок. Есть колонка ТЗ типа массив в которой находятся все возможные размещения данного отрезка на временной оси.

Захотел создать массив в котором будут все возможные варианты расположения. Простым перебором пытаюсь этот массив заполнить. Всего отрезков 11. У каждого отрезка 10-12 положений. На 5-м отрезке 1С падает и пишет что не хватает памяти ). Может не заполнять массив а просто перебирать и смотреть пересечения ? Как думаете ? Может у вас схожая задача была ?

все с временем рекламы тренируешься? :)

(shadow_sw) Ага ) Уже совсем близко конец )

по теме - а если сравнивать первый и последний элемент массива, в каждом массиве

(0) " все возможные размещения данного отрезка на временной оси" - зачем их хранить?

(shadow_sw) Сори, не понимаю тебя. Для наглядности попробую здесь подробнее описать :

Отрезок состоит из множества точек. Каждая точка в свою очередь строка ТЗ. в ТЗ две колонки "дата" и "Координата Х".

т.е. строки тз одного отрезка записываются так

01.06.2018 | 1
02.06.2018 | 1
03.06.2018 | 1

Это я показал отрезок шириной 1 клетка с 1 по 3 июня 2018 г.

(VladZ) Хотел заполнить массив всеми возможными значениями. А потом просто перебирать массив, элементами которого являются ТЗ. Это ТЗ пробовать сворачивать и сравнивать количество строк в ТЗ до свертки и после. Если количество строк не изменилось - значит ни одной повторяющейся точки нет и отрезки не пересекаются.

(6) По-моему, лажа какая-то.

Нейронную сеть писать надо...

Покажи на картинке

http://pixs.ru/showimage/Reklamajpg_7324316_30484520.jpg

(0) Давай начнем с начала. Для чего это нужно? Это тестовая задача? Или задача, имеющая какое-то практическое значение?

У отрезка есть начало и конец. Эти данные и должны храниться.

Алгоритм проверки:
- берем отрезом
- смотрим, входит ли начало этого отрезка во временной интервал других отрезков.
- смотрим, входил ли конец этого отрезка во временной интервал других отрезков.
- если ни начало, ни конец не входят - все ОК.
- идем дальше, пока не переберем все отрезки.

Покажи сабж на картинке, епта

(13) Картинка в (10)

(VladZ) Эта задача практическая. На временной оси отрезками изображены рекламные ролики. Менеджеру звонит очередной клиент и говорит параметры ролика, который он хочет чтобы запустили в эфир. т.е. говорит дату начала и дату окончания проигрывания ролика, а так же периодичность (1 раз в минуту, 1 раз в 2 минуты и т.д) и длину ролика кратную 5-ти секундам. Программа должна автоматически найти свободное место и вставить туда ролик. Если надо, то передвинув по вертикальной оси ролики, которые мешают.

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

Задача усложняется тем, что ролик повторяется, например 1 раз в минуту. На рисунке это видно. Временную ось разбили специально на 10 блоков  - 10 минут (слева от таблицы показан номер блока). Каждый блок - 1 минута. Повтор ролика 1 раз в 2 минуты будет изображен например во 2,4,6,8 и 10 блоке.

Ну и продолжительность ролика 5 секунд - 1 клетка по вертикали, 10 секунд - 2 клетки, 15 - 3 и т.д. Поэтому я решил  каждый отрезок хранить в виде координат. Чтобы узнать пересекаются отрезки или нет я просто все координаты всех отрезков сбрасываю в ТЗ с двумя колонками дата и координата по вертикали. Если после свертки ТЗ становится меньше строк - значит пересечения есть.

задачу о ранце смотрел? мне кажется можно поиграться с ней и получить довольно приемлимый результат.

(VladZ) Я так и хочу перебрать. Роликов может быть максимум 12, т.к. 5 секунд * 12 = 60, а потом идут повторы. у каждого ролика может быть 12 разных положений. Получается 12 ! возможных вариантов ? 479.001.600 ? Или я не прав ?

(Segate) Нет, не смотрел.

(21) а вообще какую-то теорию по np-полным задачам читал? Ну или в курсе что к чему? Или так, нахрапом, перебором решаешь?

(Segate) У меня "ценностей" у вещей нет, каждый отрезок должен попасть в рюкзак (отобразится на графике). )

(0) Тогда будешь ждать до старости. Такие задачи точное решение в разумное время не позволяют получить.