Codeforces Round 613 (Div. 2) |
---|
Закончено |
На координатной прямой $$$Ox$$$ заданы $$$n$$$ отрезков $$$[l_1, r_1]$$$, $$$[l_2, r_2]$$$, ..., $$$[l_n, r_n]$$$. Отрезок $$$[l, r]$$$ покрывает все точки от $$$l$$$ до $$$r$$$ включительно, то есть такие $$$x$$$, что $$$l \le x \le r$$$.
Отрезки могут располагаться произвольным образом — вкладываться друг в друга, совпадать и т.п. Отрезки могут вырождаться в точку, то есть допустимо, что $$$l_i=r_i$$$.
Объединением набора отрезков называется такой минимальный набор отрезков, который покрывает в точности тот же набор точек, что и заданный набор. Например:
Очевидно, что объединение — это набор непересекающихся отрезков.
Требуется удалить ровно один отрезок из заданных $$$n$$$ таким образом, чтобы количество отрезков в объединении оставшихся $$$n-1$$$ было наибольшим.
Например, если $$$n=4$$$ и отрезки имеют вид $$$[1, 4]$$$, $$$[2, 3]$$$, $$$[3, 6]$$$, $$$[5, 7]$$$, то:
Таким образом, в примере выше надо обязательно удалять третий отрезок, чтобы получить ответ $$$2$$$.
Напишите программу, которая найдет наибольшее количество отрезков, которые получатся в объединении $$$n-1$$$ оставшегося, если можно удалить любой из заданных $$$n$$$ отрезков.
Обратите внимание, что если в заданном наборе есть несколько одинаковых отрезков, то удалить вы всё-равно можете ровно один из них. То есть набор отрезков после удаления одного будет содержать ровно $$$n-1$$$ отрезок.
В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте. Далее следуют описания $$$t$$$ наборов входных данных.
Первая строка каждого набора содержит целое число $$$n$$$ ($$$2 \le n \le 2\cdot10^5$$$) — количество отрезков в заданном наборе. Далее в $$$n$$$ строках заданы сами отрезки парами целых чисел $$$l_i$$$, $$$r_i$$$ ($$$-10^9 \le l_i \le r_i \le 10^9$$$), где $$$l_i$$$ и $$$r_i$$$ — координаты левого и правого конца $$$i$$$-го отрезка, соответственно.
Отрезки заданы в произвольном порядке.
Гарантируется, что сумма значений $$$n$$$ по всем наборам во входных данных не превосходит $$$2\cdot10^5$$$.
Выведите $$$t$$$ чисел — ответы на заданные $$$t$$$ наборов входных данных в порядке их следования в тесте. Ответ равен максимальному количеству отрезков в объединении $$$n-1$$$ отрезка из $$$n$$$ заданных, если допускается удалить один любой отрезок.
3 4 1 4 2 3 3 6 5 7 3 5 5 5 5 5 5 6 3 3 1 1 5 5 1 5 2 2 4 4
2 1 5
Название |
---|