LINUX.ORG.RU

Максимум непересекающихся интервалов

 , ,


0

1

Задано конечное множество интервалов A. Нужно найти самое мощное подмножество множества A, интервалы которого не пересекается.



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

Ответ на: комментарий от four_str_sam

Множество, содержащее как можно больше интервалов из заданного множества так, чтобы они не пересекались.

Kotolegokot
() автор топика

вангую динамику за n*log n на сортировку

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

Видимо, искомое множество должно быть непрерывно, иначе тривиально.

four_str_sam
()

Честно говоря, задание сформулированно или совершенно невнятно, или совершенно тривиально. Если я вас правильно понял, то возьмите множество, состоящее из объединения интервалов вида ...U(0,1)U(1,2)U(2,3)U... - то есть на прямой у вас будут выколоты все натуральные числа, а остальные точки будут входить в ваше множество. Натуральных чисел - счётное число. Вся вещественная прямая континуальная. Два континуальных множества, отличающиеся друг от друга не более чем на счётное множество, равномощны. Вот и всё - найдено требуемое множество.

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

Извиняюсь, опечатался - будут выколоты все целые числа, конечно же.

Hasek ★★
()

Иди читай про жадные алгоритмы.

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

Скорее совершенно невнятно.

Вот, например, задано множество интервалов: { [3; 6]; [2; 4]; [5; 7] }. Нужно из всех его подмножеств, содержащиеся интервалы в которых не пересекаются, выделить самое мощное.

В данном случае, все такие подмножества: { [3; 6] }, { [2; 4] }, { [5; 7] }, { [2; 4]; [5; 7] }.

Самое мощное — последнее.

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

А, понял, вы не рассматриваете все вещественные точки, а считаете заданный интервал за один целый неделимый объект. Тогда могу предложить следующее:
Шаг один. Проходимся по всем заданным интервалам и смотрим, а не являются ли они сразу непересекающимися (b_i < a_i+1, если a_i - начало i-го интервала, b_i - его конец).
Шаг два. Если какие-то интервалы пересекаются (b_i > a_i+1), то смотрим, нет ли интервала, лежащего строго внутри данной пересекающейся системы интервалов (...<a_i<b_i<..., т.е. между началом и концом отрезка нет начал и концов других). Если такой интервал есть, то удаляем минимальный интервал, в котором он содержится, и возвращаемся к шагу один.
Шаг три. Если в системе пересекающихся интервалов есть интервал, принадлежащий только одному из интервалов пересекающейся системы интервалов (как в вашем примере от 4 до 5), то мы удаляем интервал, которому он принадлежит, и возвращаемся к шагу один.
Давайте попробуем поправить алгоритм, если я где-то не прав. Мог и ошибиться.

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

Не знал тоже про такой. Тогда нет проблем.

Hasek ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.