Добрый всем день. Есть следующая задача:

Существует n временных интервалов. Необходимо разбить эти интервалы на минимально возможное количество m групп таким образом, чтобы в каждой группе была бы временная точка, принадлежащая одновременно всем интервалам из группы.

Вопрос следующий - не существует ли общеизвестного алгоритма решения этой задачи? Стоит ли изобретать велосипед, или воспользоваться тем, что сделано до меня?

Заранее спасибо.

два интервала: 0-10 и 11-20. разбей

(1) Ну две группы будет.

(2) и какая точка в каждой группе принадлежит всем интервалам?

(3) В первой группе - любая, и во второй - любая. Читайте условие. :)

(1) хватит задачи из матанализа постить, уже его все забыли

Да, замечу, что задача - исключительно прикладная :)

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

непонятно условие, должны быть еще ограничения, иначе минимальное количество групп = 2: группа 1 = {все интервалы}, группа 2 = {все интервалы}

(7) Совершенно верно.

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

нуно найти наболее часто встречающиеся точки в интервалах, и от них плясать, ИМХО

Есть общеизвестный - полный перебор с отсечениями.

Вообще-то в этой задаче, минимальный набор групп получается, если просто добавлять по порядку в группы, если интервал пересекается.

То есть не полный перебор, а однократный проход...

(0) Как по условию задачи должны быть сгруппированы интералы 9-11, 10-13, 12-14?
(1,2)(3) или (1)(2,3)?

(12) нет, так даже если интервал персекается с одним он может пересекатся с большим-другим

(13) (1)(2;3)

(15) А чем не устраивает (1,2)(3)?

1234 *1
123  *2
578  *3
789  *4
87  *5

12345789
123__789
_____78

вычеркиваем оп максимальным вхождениям:
1) по семеркам *3*4*5
2) по восьмеркам неча уже вычеркивать
3) по единицам *1*2
вообщето дальше неча вычеркивать

перем начинт[100];
перем конинт[100];
перем колинт;
Функция пересекается(а,б)
   Если (начинт[а]<=начинт[б])и(конинт[а]>=начинт[б]) тогда
       возврат 1;
   иначеесли (начинт[а]>=начинт[б])и(начинт[а]<=конинт[б]) тогда    
       возврат 1;
   иначе
       возврат 0;
   Конецесли;    
Конецфункции    
Процедура Сформировать()
  колинт=4;
  начинт[1]=1;конинт[1]=10;
  начинт[2]=2;конинт[2]=3;
  начинт[3]=9;конинт[3]=12;
  начинт[4]=8;конинт[4]=11;
  начгруппы=1;        
  сообщить(""+1+" "+начинт[1]+"-"+конинт[1]);
  Для а=2 по колинт цикл  
       Для б=начгруппы по а-1 цикл
           Если пересекается(а,б)=0 тогда  
               // начинаем новую группу
               сообщить("-----");  
               сообщить(""+а+" "+начинт[а]+"-"+конинт[а]);
               начгруппы=а;
               прервать;
           КонецЕсли;    
       КонецЦикла;    
       Если начгруппы<а тогда
           // продолжается старая группа
           сообщить(""+а+" "+начинт[а]+"-"+конинт[а]);
       Конецесли;    
  Конеццикла;    
КонецПроцедуры

(16) Пардон, возможны оба варианта)) Просмотрел. И оба будут верными.

(13) какая разница какие группы, главное что их минимум две

(14) Не понимаю о чем ты. Приведи пример.

(18) Бред написал. В группу же нужно добирать до конца...
Сейчас перепишу.

(21) Ну ты предлагаешь добовлять в группу если есть пересечение, а интервал пожет персекаться с нескольками интервалами по разным перечечениям, по которым можно образовать меньше групп

Зы не заморачивайся

перем начинт[100];
перем конинт[100];
перем подобрали[100];
перем колинт;
Функция пересекается(а,б)
   Если (начинт[а]<=начинт[б])и(конинт[а]>=начинт[б]) тогда
       возврат 1;
   иначеесли (начинт[а]>=начинт[б])и(начинт[а]<=конинт[б]) тогда    
       возврат 1;
   иначе
       возврат 0;
   Конецесли;    
Конецфункции    
Процедура Сформировать()
  колинт=5;        
  Для а=1 по колинт цикл
     подобрали[а]=0;
  конеццикла;    
  начинт[1]=1;конинт[1]=10;
  начинт[2]=2;конинт[2]=4;
  начинт[3]=9;конинт[3]=12;
  начинт[4]=8;конинт[4]=11;
  начинт[5]=3;конинт[5]=4;
  Для а=1 по колинт цикл
         Если подобрали[а]=0 тогда
              // начинаем группу
              подобрали[а]=1;
              сообщить("-----");  
                сообщить(""+а+" "+начинт[а]+"-"+конинт[а]);
                списподобранных=создатьобъект("списокзначений");
                списподобранных.добавитьзначение(а);
                Для б=а+1 по колинт цикл
                   Если подобрали[б]=1 тогда
                       продолжить;
                   Конецесли;                                    
                   подходит=1;
                   для в=1 по списподобранных.размерсписка() цикл
                       Если пересекается(б,списподобранных.получитьзначение(в))=0 тогда
                           подходит=0;
                           прервать;
                       Конецесли;    
                   Конеццикла;      
                   Если подходит=1 тогда
                       // добавляем в группу  
                       подобрали[б]=1;
                       списподобранных.добавитьзначение(б);
                       сообщить(""+б+" "+начинт[б]+"-"+конинт[б]);
                   Конецесли;    
                Конеццикла;    
         КонецЕсли;    
  Конеццикла;        
КонецПроцедуры

(23) Приведи пример. Не может.

(0) а время дискретно?

(26) Да. Минимальная частица - секунда.

Хотя наверно действительно может дать неоптимальное разбиение, но даже если это так - это экзотика, сходу даже пример не придумать.

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

12345 *1
12    *2
2345  *3
23456 *4

Начинаем перебирать *1 и *2 Пересекаются по 1,2 и 12, но все 4 закрываются по 2

(28) Вам - спасибо. Сейчас буду разбирать ваши алгоритмы :)

(29) Хотя конечно наверное можно извернуться с обработкой данных долями и очисткой памяти.

а отсортировать интервалы по возрастанию и положению на временной оси не предлагать?

(33) А зачем?

(34) угу, не совсем то ...

(32) В реальной задаче каково количество анализируемых интервалов?

(30) Ну и? Берем первый интервал, добавляем к нему второй, третий и четвертый. Получаем одну группу. Такой результат код (24) и выдаст.

границаНабора = ОтсортированныеПоДатеНачалаИнтервалы[0].ВремяОкончания;
группа = Новый Массив
массивГрупп = Новый Массив
Для каждого интервал Из ОтсортированныеПоДатеНачалаИнтервалы Цикл
  Если интервал.ВремяНачала > границаНабора Тогда
      массивГрупп.Добавить(группа);
      группа.Очистить();
      границаНабора = интервал.ВремяОкончания;
  Иначе
      границаНабора = Мин(интервал.ВремяОкончания, границаНабора);
  КонецЕсли;
  группа.Добавить(интервал);
КонецЦикла;
массивГрупп.Добавить(группа);

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

вчера не успел подумать на работе, по дороге домой посчитал

(38) (39)
Этот алгоритм не может быть оптимальным.
Так как мой алгоритм в лучшем случае работает за О(N), а твой всегда за О(N ln N)
Правда в худшем случае (когда один интервал) мой алгоритм работает за О(N^2)

(40) а ты не считал количество операций в итерации у себя и у меня?

я понимаю, что еще сортировка, но это вполне окупится

(41) Вообще-то принято считать сложность алгоритма, а не итерации. то есть О() от количества итераций. У тебя за счет сортировки всегда Эн логарифмов.

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

Представим задачу (для дискретного случая) в виде двудольного графа (ИНТЕРВАЛЫ, ЧИСЛА). Вершинами доли ИНТЕРВАЛЫ будут интервалы, вершинами доли ЧИСЛА будут числа, входящие в интервалы. Дуга от вершины ИНТЕРВАЛ к вершине ЧИСЛО будет если число входит в интервал.
Тогда, если НЕ ошибаюсь, задача заключается в том, чтобы найти минимальное множество вершин доли ЧИСЛА, так чтобы из него были видны ВСЕ интервалы. ВОЗМОЖНО, здесь работает жадный алгоритм: брать число, которое входит в максимальное число интервалов - это будет "представитель" 1-ой группы, группу составят интервалы, которым число принадлежит, удалить число и интервалы из графа, повторить.
Для примера выше (интервалы обозначил буквами):
а(1234), б(123), в(578). г(789), д(78).
Для чисел вхождение в интервалы:
1(аб), 2(аб), 3(аб), 4(а), 5(в), 7(вгд), 8(вгд), 9(г).
1-я группа - число 7 (или 8), интервалы (вгд)
2-я группа - число 1 (или 2), интервалы (аб).

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

(45) Найди пример когда (24) или (38) не дадут лучший результат.

(46) Того, что 24 или 38 неоптимальны я не утверждал. Хочется понять характер задачи.

(47) Задача ИМХО не сводится к теории графов в явном виде.

(48) Буду признателен, если укажите, где неправ: сам дыры не нашел.

(49) Дыра в сложности алгоритма и в количестве вершин графа. Числа вообще могут быть не дискретны. И даже если они дискретны полиномиальным алгоритм от количества интервалов быть не может, так как количество чисел у нас вообще от количества интервалов не зависит.

Хотя можно числами считать только крайние границы интервалов.
Тогда вы прийдете к методу в (24) и (38)

(51) Возможно жадный алгоритм и совпадает с (24), (38). Пока открыт вопрос, является ли жадный алгоритм оптимальным.

(45) По теории графов можно еще по-другому эту задачу представить:
Вершины графа - это интервалы.
Дуга между вершинами - интервалы имеют общую точку.

Тогда, задача сводится к разбитию графа на минимальное количество "полных" подграфов. Естественно, после выделения очередного полного подграфа, дуги, соединяющие его с основным, удаляются.

(53) На первый взгляд это справедливо, если интервалы не "дырявые".
Известно, что поиск максимальной клики - NP-полная задача (правда, неочевидно, что интервалами можно породить произвольный граф). Для этой задачи неплохо работает алгоритм Брона — Кербоша wiki:Алгоритм_Брона_%E2%80%94_Кербоша
Может поиск минимального числа клик проще?

(54) угу, только сначала надо построить графы

(55) Разве здесь есть какая-то проблема?

(56) время

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

как это?

Интервал это или точка или отрезок, ну а далее: "точка" может быть до начала, равна началу, внутри, равна концу, за концом (всего 5 позиций).
Если "отрезок то может не пересекать до начала, пересекать 2-й интервал, заканчиваться в начале 2-го, начинаться в начале 2-го, начинаться в конце 2-го, находиться внутри 2-го "отрезка", включать в себя 2-й "отрезок", заканчиваться в конце 2-го, находиться после 2-го и т.д.

Всего может быть 16 положений временных интервалов на прямой относительно друг друга (если каждым интервалом можно считать и "точку"(нулевая длительность ДатаНачала = ДатаОкончания) или "отрезок" (ДатаНачала < ДатаОкончания).

(0) Обычная задачка на пересечение множеств. Причём множества - конечные.

Задача оказалась не так проста: в случае "дырявых" интервалов она эквивалента (45) NP-полной задаче о покрытии wiki:Задача_о_покрытии_множества
Жадный алгоритм (45) не дает оптимального решения: пример в той же статье в Википедии.
Для "сплошных" интервалов пример из Википедии не годится.

(0) по-моему условие вообще некорректно поставлено:
либо приводите все временные интервалы к единой т.о. и используйте полярные координаты для отсечения "групп" и точек в них (естесственно, все интревалы внутри групп будут равны), либо - то же самое, но с другого боку: определитесь, чем ограничена группа (каждая из m-множества групп), чтобы найти максимально входящее в каждую группу число неделимых интервальчиков (в данном случае - это секунды), и уже это принять за базу и строить отсюда какие-то теории.
Иначе бессмысленно условие "минимально возможное количество групп" - все зависит, где я проведу границу группы: у этого исходного интервала эта секунда попадает во все интервалы группы, а эта - не попадает; делаю границу группы другой - все наоборот.
И получается, что минимальное количество групп равно количеству минимальных неделимых частичек (в данной задаче - секунды), которые являются просто общими для всех интервалов: разбейте еще мельче (полсекунды, четверть секунды) - и количество искомых групп возрастет в соответствии с новым измельчением.

(63) ну вот приехали