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

Что такое

множествa с наибольшей возможной мощностью непересекающихся интервалов

?

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

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

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

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

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

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

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

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

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

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

Нашел тут решение: https://ru.wikipedia.org/wiki/%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC

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

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