Codeforces Round 661 (Div. 3) |
---|
Закончено |
Вам даны $$$n$$$ отрезков на координатной оси $$$OX$$$. $$$i$$$-й отрезок имеет границы $$$[l_i; r_i]$$$. Все точки $$$x$$$, для которых выполняется условие $$$l_i \le x \le r_i$$$, принадлежат $$$i$$$-му отрезку.
Ваша задача — выбрать такое максимальное по размеру (количеству отрезков) подмножество заданного множества отрезков, что каждая пара отрезков в этом подмножестве либо не пересекается либо же один из них лежит внутри другого.
Два отрезка $$$[l_i; r_i]$$$ и $$$[l_j; r_j]$$$ не пересекаются, если у них нет общих точек. Например, отрезки $$$[1; 2]$$$ и $$$[3; 4]$$$, $$$[1; 3]$$$ и $$$[5; 5]$$$ не пересекаются, а отрезки $$$[1; 2]$$$ и $$$[2; 3]$$$, $$$[1; 2]$$$ и $$$[2; 2]$$$ пересекаются.
Отрезок $$$[l_i; r_i]$$$ лежит внутри отрезка $$$[l_j; r_j]$$$, если $$$l_j \le l_i$$$ и $$$r_i \le r_j$$$. Например, отрезки $$$[2; 2]$$$, $$$[2, 3]$$$, $$$[3; 4]$$$ и $$$[2; 4]$$$ лежат внутри отрезка $$$[2; 4]$$$, а $$$[2; 5]$$$ и $$$[1; 4]$$$ — нет.
Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.
Первая строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 3000$$$) — количество отрезков. Следующие $$$n$$$ строк описывают отрезки. $$$i$$$-й отрезок задан двумя целыми числами $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$), где $$$l_i$$$ — левая граница $$$i$$$-го отрезка, а $$$r_i$$$ — правая граница $$$i$$$-го отрезка.
Дополнительное ограничение на входные данные: в заданном списке отрезков нет дубликатов.
Гарантируется, что сумма $$$n$$$ не превосходит $$$3000$$$ ($$$\sum n \le 3000$$$).
Для каждого набора тестовых данных выведите ответ: максимально возможный размер такого подмножества заданного множества отрезков, что каждая пара отрезков в этом подмножестве либо не пересекается, либо же один из них лежит внутри другого.
4 4 1 5 2 4 2 3 3 4 5 1 5 2 3 2 5 3 5 2 2 3 1 3 2 4 2 3 7 1 10 2 8 2 5 3 4 4 4 6 8 7 7
3 4 2 7
Название |
---|