Олимпиадный тренинг

Задача . F. Кормление кошек


Задача

Темы: дп сортировки Структуры данных *1900

Существует увлекательная игра, в которой вам нужно кормить кошек, которые приходят и уходят. Уровень игры состоит из \(n\) шагов. Есть \(m\) кошек; кошка \(i\) присутствует на шагах от \(l_i\) до \(r_i\), включительно. На каждом шаге вы можете покормить всех кошек, которые в данный момент присутствуют, или ничего не делать.

Если вы кормите одну и ту же кошку более одного раза, она переест, и вы сразу проиграете игру. Ваша цель — покормить как можно больше кошек, не заставив ни одну из них переесть.

Найдите максимальное количество кошек, которых вы можете покормить.

Формально вы должны выбрать несколько целочисленных точек из отрезка от \(1\) до \(n\) так, чтобы среди данных отрезков ни один не покрывал две или более из выбранных точек и как можно больше отрезков покрывали одну из выбранных точек.

Входные данные

Первая строка ввода содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных. Затем следуют описания наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа \(n\) и \(m\) (\(1 \le n \le 10^6\), \(1 \le m\le 2\cdot 10^5\)).

\(i\)-я из следующих \(m\) строк содержит пару целых чисел \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le n\)).

Сумма \(n\) для всех тестов не превышает \(10^6\), сумма \(m\) для всех тестов не превышает \(2\cdot 10^5\).

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное количество кошек, которых вы можете покормить.

Примечание

В первом примере один из способов покормить пять кошек — это покормить их на шагах \(4\) и \(11\).

  • На шаге \(4\) будут покормлены кошки \(1\), \(2\) и \(3\).
  • На шаге \(11\) будут покормлены кошки \(5\) и \(6\).

Примеры
№Входные данныеВыходные данные
1 3
15 6
2 10
3 5
2 4
7 7
8 12
11 11
1000 1
1 1000
5 10
1 2
3 4
3 4
3 4
3 4
1 1
1 2
3 3
3 4
3 4 
5
1
10

time 3000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет