Дано конечный набор множеств чисел
(1, 2), (2, 3), (4, 5)
Нужно разбить эти множества на непересекающиеся классы
(1, 2), (2, 3) и (4, 5)
или показать что такого разбиения нет

такое разбиение есть всегда, просто оно может состоять из одного класса

в чем вопрос то? ну делаешь перебор и смотришь ))

(1) 1 класс - считаем что нет разбиения
Вопрос в алгоритме, кроме перебора
Хотя бы понять как такая задача называется

(3) Криво задача сформулирована.
Есть такая задача. Олимпиадная формулировка.
В классе некоторые ученики дружат друг с другом.
Разбить класс на группы так, чтоб ни в какой группе не было двух друзей. Оно?

если одно множество входит во второе, а третье с ним пересекается, то можно не проверять перебором второе и третье. в остальном только перебором (мне думается).

в чем проблема то? в каком типе хранить границы отрезков?)

(6) это не отрезки :)

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

(4) не совсем оно.
(8) Это и есть перебор ))

необязательно по 2 элемента в множестве. Можно так
(1, 2, 3), (3), (4, 5)

а зачем тебе это?

(10)И? Чем это не соотвествует (4)?
В четыре запрещено троим попарно дружить?

(12) Нет не запрещено. Тогда получается что эта задача

(7) почему не отрезки? они родимые вроде, как бонус подхода упорядоченность и легкость склейки. Обозвать коробки отрезками и получить бонус

(13) Если разбить нужно на две группы - то задача очень простая.

Идея: поиск в ширину.
Берем 1 множество. Ищем все другие пересекающиеся с 1. Добавляем к нему все элементы этих множеств и тд

Хотя, явно не на две, а на минимально возможное...

(15) Чем больше групп тем лучше

(18) Каждое число - это отдельная группа. Вот и всё решение.

(19) чисел самих по себе нет. Есть множества

(19) нет не та задача. Эта задача - разбить класс на группы, так чтобы никто не дружил друг с другом из разных групп

(20) Каждое множество состоит из одного числа.

(22) но в моем условии не так

(23) Так напиши понятней. А то у тебя в ответе в (0) два множества пересекаются.

Если два множества пересекаются - считаем что они дружат друг с другом - свели к  (4)

Можно так сформулировать (про учеников):
Ученики в классе увлекаются: спортом, математикой, пением и тд.
Один ученик может увлекаться разными занятиями
Нужно сформировать кружки так чтобы все интересы всех учеников были учтены.
Можно формировать кружки типа: математика+пение

(25) Противоположная задача: У тебя ни в какой группе двух друзей. У меня - в группе только друзья

(24) два множества A[0] и A[N] из набора лежат в одном классе, если найдется цепочка множеств A[1],...,A[N-1] из этого набора множеств, что:
для любого 0<=i<N A[i]?A[i+1] не пусто

кстати можно на графах задачу рассматривать: Найти все несвязные подграфы

+(28) вместо вопроса знак пересечения

(29) пожалуй это и будет правильной формулировкой задачи

(31) и поиск в ширину будет самым оптимальным решением