Это простая версия задачи. В этой версии ограничения на \(n\) и ограничение по времени ниже. Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Назовём множество (замкнутых) отрезков сложным, если оно может быть разбито на некоторые подмножества так, что
- все подмножества имеют одинаковый размер; и
- пара отрезков пересекается тогда и только тогда, когда эти два отрезка находятся в одном и том же подмножестве.
Вам даны \(n\) отрезков \([l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]\). Найдите максимальный размер сложного подмножества этих отрезков.
Выходные данные
Для каждого набора входных данных выведите одно целое число: максимальный размер сложного подмножества заданных отрезков.
Примечание
В первом наборе входных данных все пары отрезков пересекаются, поэтому оптимально сформировать одну группу, содержащую все три отрезка.
Во втором наборе входных данных не существует подходящего разбиения для всех пяти отрезков. Корректное разбиение с четырьмя отрезками выглядит следующим образом: \(\{\{ [1, 5], [2, 4] \}, \{ [6, 9], [8, 10] \}\}\).
В третьем наборе входных данных оптимально составить одну группу, содержащую все отрезки, кроме второго.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 2 3
5 4 6
5
1 2 3 6 8
5 4 7 9 10
5
3 1 4 1 5
7 2 6 5 10
|
3
4
4
|