Найдите наименьшую часть пересекающихся интервалов
Учитывая набор целочисленных интервалов SI = {I1,I2,...,In}, мне нужно найти наименьший раздел SI такой, что все интервалы подмножества раздела пересекаются.
То есть найдите наименьшее P = {Pi : Pi⊂SI}, где Pi∩Pj=∅
и такое, что ∀Ia,Ib∊Pi, Ia∩Ib≠∅
Например :
Дано, SI = {[0,7],[0,6],[1,2],[4,10],[5,10],[9,10]}
Результат должен быть P* = {{[0,7],[0,6],[1,2]},{[4,10],[5,10],[9,10]}}, где |Р*|=2
Как называется эта проблема в литературе? Кто-нибудь может подсказать эффективный оптимальный алгоритм?
Мое текущее решение является жадным, когда я итеративно нахожу максимальные перекрывающиеся интервалы (используя подпрограмму временной сложности O (nlogn)). Для данного примера это выводит раздел P = {{[0,7],[0,6],[4,10],[5,10]},{[1,2]},{[9, 10]}} размера 3.
Я бы назвал эту проблему «разделение клики »: I_i — это вершины в графе, и вы хотите разделить граф на клики. Кроме того, это интервальный график, который значительно упрощает задачу.
Ответы 2
I_i образуют граф. Этот граф является интервальным графом , что означает, что легко найти совершенный порядок исключения его вершин.
Возьмем самый левый интервал I, т.е. интервал [a, b] с наименьшим b. Убедите себя, что для любых двух других интервалов J и K, если J и K пересекаются с I, то J и K также пересекаются друг с другом. Таким образом, множество, состоящее из I, а также каждый интервал, который пересекает I, является кликой и может быть первым множеством вашего разбиения.
Удалите интервалы из этого первого набора, затем повторите процедуру, чтобы получить другие наборы.
Спасибо за терминологию и ссылки. Мне нравится "кликовый раздел". Я согласен со свойством, которое вы утверждаете для I,J,K, принадлежащих одной и той же клике P_i.
Если я хорошо понимаю. То, что вы предлагаете, является жадным решением, подобным тому, которое я предложил, но принятие идеального порядка исключения позволяет использовать подпрограмму O (n).
@ JMAziz Да, это «жадно, но в правильном порядке», поэтому на самом деле возвращает оптимальное решение. На самом деле многие задачи можно решить таким образом для графов с идеальным порядком исключения.
@ JMAziz Обратите внимание, что мы с MattTimmermans описываем один и тот же алгоритм, только разными словами.
На самом деле, я посмотрел на ваш, прежде чем писать, но вы говорите «возьмите интервал [a,b] с наименьшим a», тогда как я говорю, возьмите интервал с наименьшим b. Если взять наименьшее a, ваше следующее предложение станет неверным, например, [ [ ] [ ] ] Я думаю, это была небольшая ошибка, но не было ясно, правильно ли то, что вы имели в виду в целом.
да, он должен был быть самым маленьким b. Я думал, вы доказываете, что каждое разбиение является кликой в интервальном графе. Не видел, чтобы вы предлагали тот же алгоритм, что и Мэтт:/
Действительно! Самый маленький б.
- Найдите интервал с наименьшей конечной точкой. Некоторое подмножество должно включать этот интервал
- Создайте подмножество с выбранным интервалом и всеми интервалами, которые начинаются до этой наименьшей конечной точки. Все они пересекаются друг с другом, поскольку все они включают интервал непосредственно перед этой наименьшей конечной точкой. Кроме того, любой интервал, который начинается позже, не перекрывается с выбранным и не может быть включен в то же подмножество.
- Повторяйте, пока не закончатся интервалы.
Обычно вы начинаете с сортировки интервалов по конечной точке, что делает все это быстрым и легким.
просто и легко. Спасибо.
Вместо этого попробуйте задать вопрос на Stack Overflow на русском.