Здравствуйте. Есть исходная таблица "События"(табличная часть документа). Нужно составить из этих событий расписание таким образом, чтобы можно было посетить как можно больше событий(от его начала и до конца). Подскажите, пожалуйста куда нужно копать или ,может какой-нибудь алгоритм для решения этой задачи.
Прикладываю скриншот исходной таблицы и таблицы результатов.
---
Доработал алгоритм, чтобы проход был максимально линейным, но как его полноценно протестировать - непонятно.

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

Если убрать повторяющиеся, то остается меньше тысячи, и скорость работы приемлемая, а в итогах по траектории записей меньше 10.

Но повторюсь - для уверенности надо хорошо потестировать.

```1c
    &НаСервере
    Процедура СформироватьОтчетНаСервере()
    Запрос = Новый Запрос;
    Запрос.Текст =
    "ВЫБРАТЬ РАЗЛИЧНЫЕ
    | СобытияСписокСобытий.ВремяНачала КАК ВремяНачала,
    | СобытияСписокСобытий.Длительность КАК Длительность
    |ИЗ
    | Документ.События.СписокСобытий КАК СобытияСписокСобытий
    |ГДЕ
    | СобытияСписокСобытий.Ссылка = &Ссылка
    |
    |УПОРЯДОЧИТЬ ПО
    | ВремяНачала";
    Запрос.УстановитьПараметр("Ссылка", ВыбранныйДокумент.Ссылка);
    РезультатЗапроса = Запрос.Выполнить();
    Если РезультатЗапроса.Пустой() Тогда
    Возврат;
    КонецЕсли;

    ТЗ = Запрос.Выполнить().Выгрузить();
    ТЗ.Колонки.Добавить("КолВоПосещений");
    ТЗ.Колонки.Добавить("НомерПредшественника");

    ТЗ[0].КолВоПосещений = 1;
    ТЗ[0].НомерПредшественника = -1;
    ИндексСтрокиСМаксимальнымПосещением = 0;

    Для Счетчик = 1 По ТЗ.Количество()-1 Цикл

    ТЗ[Счетчик].КолВоПосещений = 1;
    ТЗ[Счетчик].НомерПредшественника = -1; // заглушка, чтобы не опускаться глубже

    ВложенныйСчетчик = Счетчик-1;
    Пока ВложенныйСчетчик >= 0 ЦИКЛ
    ТекСтрока = ТЗ[ВложенныйСчетчик];
    Если ТЗ[Счетчик].ВремяНачала >= ТекСтрока.ВремяНачала + ТекСтрока.Длительность*60 Тогда
    ТЗ[Счетчик].НомерПредшественника = ВложенныйСчетчик;
    ТЗ[Счетчик].КолВоПосещений = ТекСтрока.КолВоПосещений + 1;

    Если ТЗ[ИндексСтрокиСМаксимальнымПосещением].КолВоПосещений <= ТЗ[Счетчик].КолВоПосещений Тогда
    ИндексСтрокиСМаксимальнымПосещением = Счетчик;
    КонецЕсли;
    Прервать;
    КонецЕсли;

    ВложенныйСчетчик = ВложенныйСчетчик - 1;
    КонецЦикла;

    КонецЦикла;

    //обратным ходом восстанавливаем последовательность к элементу с максимальным кол-вом посещений
    ОптимальнаяТраектория = Новый Массив;
    ОптимальнаяТраектория.Добавить(ИндексСтрокиСМаксимальнымПосещением);

    ТекущийИндекс = ИндексСтрокиСМаксимальнымПосещением;
    Пока ТЗ[ТекущийИндекс].НомерПредшественника >= 0 Цикл
    ОптимальнаяТраектория.Вставить(0, ТЗ[ТекущийИндекс].НомерПредшественника);
    ТекущийИндекс = ТЗ[ТекущийИндекс].НомерПредшественника;
    КонецЦикла;

    Для каждого Элемент Из ОптимальнаяТраектория Цикл
    Сообщить("Время: " + ТЗ[Элемент].ВремяНачала + ", длительность: " + ТЗ[Элемент].Длительность);
    КонецЦикла;

    КонецПроцедуры
```
---
Построить дерево значений (граф), найти ветвь с максимальным количеством узлов.
---
Похоже на задачи по динамическому программированию. Посмотрите решение задачи о кузнечике, которые прыгает с разными интервалами
---
Я бы нашёл участки, которые содержат более одного события и исключал бы конфликтующие события. События, содержащие больше конфликтов должны быть в приоритете к исключению.
---
Навсидку, примерно так (делал на коленке, можно оптимизировать, конечно)

```1c
    &НаСервере
    Процедура ОптимальныеСобытия()

    ТЗ = Новый ТаблицаЗначений;
    ТЗ.Колонки.Добавить("ВремяНачала", Новый ОписаниеТипов("Дата",,,Новый КвалификаторыДаты(ЧастиДаты.Время)));
    ТЗ.Колонки.Добавить("ДлительностьВМинутах");

    ЗаполнениеТаблицыСобытий(ТЗ);

    ТЗ.Сортировать("ВремяНачала");
    СписокНаибольшихЗначений = Новый СписокЗначений;
    // в значение записываем максимум посещений для данной точки, в представление - оптимальную траекторию
    СписокНаибольшихЗначений.Добавить(1, "0"); // в первую точку можно попасть только одним способом из предшественника с индексом 0

    Для Счетчик = 1 По ТЗ.Количество()-1 Цикл
    КолВоМаксПосещений = 1; // посещение текущей точки

    Для ВложенныйСчетчик = 0 По Счетчик-1 Цикл
    Если ТЗ[Счетчик].ВремяНачала >= ТЗ[ВложенныйСчетчик].ВремяНачала + ТЗ[ВложенныйСчетчик].ДлительностьВМинутах*60 Тогда
    Если СписокНаибольшихЗначений[ВложенныйСчетчик].Значение + 1 > КолВоМаксПосещений Тогда
    КолВоМаксПосещений = СписокНаибольшихЗначений[ВложенныйСчетчик].Значение + 1;
    ОптимальныйПредшественник = ВложенныйСчетчик;
    КонецЕсли;
    КонецЕсли
    КонецЦикла;

    // добавляем в массив оптимальную траекторую для данной точки
    Если КолВоМаксПосещений >1 Тогда
    Траектория = СписокНаибольшихЗначений[ОптимальныйПредшественник].Представление + "," + Счетчик;
    Иначе
    Траектория = Строка(Счетчик);
    КонецЕсли;

    СписокНаибольшихЗначений.Добавить(КолВоМаксПосещений, Траектория);
    КонецЦикла;

    СписокНаибольшихЗначений.СортироватьПоЗначению(НаправлениеСортировки.Убыв);
    ОптимальнаяТраектория = СтрРазделить(СписокНаибольшихЗначений[0].Представление, ",");

    Для каждого Элемент Из ОптимальнаяТраектория Цикл
    Сообщить("Время: " + ТЗ[Число(Элемент)].ВремяНачала + ", длительность: " + ТЗ[Число(Элемент)].ДлительностьВМинутах);
    КонецЦикла;

    КонецПроцедуры
```
---
Здравствуйте. Почему-то результат без события №7 и на других примерах выдает неверные результаты. А на таблице с около 10000 записей программа зависает.
---
А на таблице с около 10000 записей программа зависает.Ну так 10000 * 5000 = 50 000 000 (50 млн) итераций. Да и не должно оно правильно работать, ибо (дальше много непонятных слов).
---
Фактически, задача про все варианты выбранных мероприятий без пересечений. Таких вариантов <= чем 2^К, где К - количество вариантов. Самый простой метод - это битовое значение. Количество бит = количество событий. Бит = 1 - идем, бит = 0 - не идем. Дальше тест на допустимость, что события не пересекаются. Дальше поиск варианта, где полезного времени больше, чем в других вариантах (таких вариантов может быть несколько). Ну и всяческие эвристики можно сюда нагнетать, если охота. Но для 20-ти событий - это цикл от единицы до миллиона с чем-то - не сильно то и много даже для 1С.
---
Напишите ожидаемый результат без события №7 и пару других примеров с результатами
---
Прошу прощения, это я что-то перепутал, Ваш код работает правильно. Не подскажите, как его можно оптимизировать, чтобы он смог работать с большим объемом записей?
---
Не совсем уверен в этом коде, попробуйте потестировать на маленьких выборках на верность.
Если работает правильно, попробуйте на больших (количество вложенных итераций должно существенно сократиться), и в замере производительности гляньте, где больше всего съедается времени.
Подозреваю, что на сортировках таблиц и СтрРазделить

```1c
    &НаСервере
    Процедура ОптимальныеСобытияРеф()

    ТЗ = Новый ТаблицаЗначений;
    ТЗ.Колонки.Добавить("ВремяНачала", Новый ОписаниеТипов("Дата",,,Новый КвалификаторыДаты(ЧастиДаты.Время)));
    ТЗ.Колонки.Добавить("ДлительностьВМинутах");

    ЗаполнениеТаблицыСобытий(ТЗ);

    ТЗ.Сортировать("ВремяНачала");

    ТаблицаМаксимумов = Новый ТаблицаЗначений;
    ТаблицаМаксимумов.Колонки.Добавить("ВремяОкончания");
    ТаблицаМаксимумов.Колонки.Добавить("КолВоПосещений");
    ТаблицаМаксимумов.Колонки.Добавить("Траектория");

    Максимум = ТаблицаМаксимумов.Добавить();
    Максимум.ВремяОкончания = ТЗ[0].ВремяНачала + ТЗ[0].ДлительностьВМинутах*60;
    Максимум.КолВоПосещений = 1;
    Максимум.Траектория = "0";

    Для Счетчик = 1 По ТЗ.Количество()-1 Цикл

    КолВоПосещений = 1;
    Траектория = Строка(Счетчик);

    ВложенныйСчетчик = ТаблицаМаксимумов.Количество() - 1;
    Пока ВложенныйСчетчик >= 0 ЦИКЛ
    ТекМаксимум = ТаблицаМаксимумов[ВложенныйСчетчик];
    Если ТЗ[Счетчик].ВремяНачала >= ТекМаксимум.ВремяОкончания Тогда

    КолВоПосещений = ТекМаксимум.КолВоПосещений + 1;
    Траектория = ТекМаксимум.Траектория + "," + Счетчик;
    Прервать;
    КонецЕсли;

    ВложенныйСчетчик = ВложенныйСчетчик - 1;
    КонецЦикла;

    НовыйМаксимум = ТаблицаМаксимумов.Добавить();
    НовыйМаксимум.ВремяОкончания = ТЗ[Счетчик].ВремяНачала + ТЗ[Счетчик].ДлительностьВМинутах*60;
    НовыйМаксимум.КолВоПосещений = КолВоПосещений;
    НовыйМаксимум.Траектория = Траектория;

    КонецЦикла;

    ТаблицаМаксимумов.Сортировать("КолВоПосещений убыв");

    ОптимальнаяТраектория = СтрРазделить(ТаблицаМаксимумов[0].Траектория, ",");

    Для каждого Элемент Из ОптимальнаяТраектория Цикл
    Сообщить("Время: " + ТЗ[Число(Элемент)].ВремяНачала + ", длительность: " + ТЗ[Число(Элемент)].ДлительностьВМинутах);
    КонецЦикла;

    КонецПроцедуры
```
---
На маленьких работает хорошо, на большой выборке виснет намертво.
---
Вот замеры производительности
---
Надо в отладке смотреть. Вы на сервере вычисления делаете? Таблицу с большой выборкой можете прислать?
---
Вот выгрузка, проверяю через отчет "Расписание".
---
Доработал алгоритм, чтобы проход был максимально линейным, но как его полноценно протестировать - непонятно.

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

Если убрать повторяющиеся, то остается меньше тысячи, и скорость работы приемлемая, а в итогах по траектории записей меньше 10.

Но повторюсь - для уверенности надо хорошо потестировать.

```1c
    &НаСервере
    Процедура СформироватьОтчетНаСервере()
    Запрос = Новый Запрос;
    Запрос.Текст =
    "ВЫБРАТЬ РАЗЛИЧНЫЕ
    | СобытияСписокСобытий.ВремяНачала КАК ВремяНачала,
    | СобытияСписокСобытий.Длительность КАК Длительность
    |ИЗ
    | Документ.События.СписокСобытий КАК СобытияСписокСобытий
    |ГДЕ
    | СобытияСписокСобытий.Ссылка = &Ссылка
    |
    |УПОРЯДОЧИТЬ ПО
    | ВремяНачала";
    Запрос.УстановитьПараметр("Ссылка", ВыбранныйДокумент.Ссылка);
    РезультатЗапроса = Запрос.Выполнить();
    Если РезультатЗапроса.Пустой() Тогда
    Возврат;
    КонецЕсли;

    ТЗ = Запрос.Выполнить().Выгрузить();
    ТЗ.Колонки.Добавить("КолВоПосещений");
    ТЗ.Колонки.Добавить("НомерПредшественника");

    ТЗ[0].КолВоПосещений = 1;
    ТЗ[0].НомерПредшественника = -1;
    ИндексСтрокиСМаксимальнымПосещением = 0;

    Для Счетчик = 1 По ТЗ.Количество()-1 Цикл

    ТЗ[Счетчик].КолВоПосещений = 1;
    ТЗ[Счетчик].НомерПредшественника = -1; // заглушка, чтобы не опускаться глубже

    ВложенныйСчетчик = Счетчик-1;
    Пока ВложенныйСчетчик >= 0 ЦИКЛ
    ТекСтрока = ТЗ[ВложенныйСчетчик];
    Если ТЗ[Счетчик].ВремяНачала >= ТекСтрока.ВремяНачала + ТекСтрока.Длительность*60 Тогда
    ТЗ[Счетчик].НомерПредшественника = ВложенныйСчетчик;
    ТЗ[Счетчик].КолВоПосещений = ТекСтрока.КолВоПосещений + 1;

    Если ТЗ[ИндексСтрокиСМаксимальнымПосещением].КолВоПосещений <= ТЗ[Счетчик].КолВоПосещений Тогда
    ИндексСтрокиСМаксимальнымПосещением = Счетчик;
    КонецЕсли;
    Прервать;
    КонецЕсли;

    ВложенныйСчетчик = ВложенныйСчетчик - 1;
    КонецЦикла;

    КонецЦикла;

    //обратным ходом восстанавливаем последовательность к элементу с максимальным кол-вом посещений
    ОптимальнаяТраектория = Новый Массив;
    ОптимальнаяТраектория.Добавить(ИндексСтрокиСМаксимальнымПосещением);

    ТекущийИндекс = ИндексСтрокиСМаксимальнымПосещением;
    Пока ТЗ[ТекущийИндекс].НомерПредшественника >= 0 Цикл
    ОптимальнаяТраектория.Вставить(0, ТЗ[ТекущийИндекс].НомерПредшественника);
    ТекущийИндекс = ТЗ[ТекущийИндекс].НомерПредшественника;
    КонецЦикла;

    Для каждого Элемент Из ОптимальнаяТраектория Цикл
    Сообщить("Время: " + ТЗ[Элемент].ВремяНачала + ", длительность: " + ТЗ[Элемент].Длительность);
    КонецЦикла;

    КонецПроцедуры
```
---
Приемлемая это сколько?
---
Попробуйте) несколько секунд на файловой базе
---
Я с учебной версии это делаю. Это как то влияет?
---
У меня документ, где 13к записей обрабатывает примерно минут 8. Может быть я что-то не так делаю?
---
Текст запроса к ТЧ документа и дальнейший код скопировали из (16)?
Сколько записей в ТЗ, полученной из запроса (отсортированной и без повторяющихся)? (посмотрите в отладке до начала цикла по её строкам)
---
А вот если мне запросом ещё нужно получить поля "Тема события" и "Номер строки", то как быть?
---
Если все равно, какое событие посетить из начинающихся в один момент и с одинаковой длительностью, то в первом запросе это получать не нужно. Лучше после формирования конечной оптимальной цепочки Время/Длительность присоединить к ней данные по Тема/НомерСтроки из любой записи исходной таблицы с таким же Временем и Длительностью.
---
Спасибо Вам! Вы - гений!)