Хоть бы "пожалуйста" сказал

Эта ДП, строится так.

// Ts, Te <= 30000
int dp[30002]; // dp[i] - это максимум количество сменарий которые можно участвовать, до i-той минуты.
int e[30002]; //  e[i] - это максимальная начальная время из всех сменарий которые Ts == i.

//  e[i] = 0, i = 0..30002  initialization.
//  for i = 0..n-1    e[ te ] = max(e[te], ts); // ts, te - начальная и конечная время сменарий.

//  dp[0] = 0.

//  i = 1..30002  :   
//     1. dp[i] = dp[i-1] ; // i - той минуты никакой сменарий нет, тогда dp[i] - равен предыдушее.
//     2.    вот здесь может закончились какое нибуд сменарий в i-той минут, нам нужен такой сменарий, который  начался позднее из всех ,  т.е. e[i] - Это начальная время интересующиее нам сменарий.
  Поэтому,  если  e[i] > 0  ( это означает действительно есть хотя бы один сменарий), тогда
       dp[i] = max(dp[i],  1 + dp[ e[i] - 1] ).


Ну конечно, dp[30001] - Ответь ).

В этой задаче работает жадность. Давайте отсортим пары (T_e, T_s). Теперь покажем, что можно брать элементы в порядке этой сортировки, если T_sⁱ > T_e^j, где j — последний взятый элемент, а i — текущий просматриваемый. Изначально возьмем первую пару, понятно что так как она заканчивается раньше всех, то не имеет смысла брать никакую другую пару. Теперь уберем все пары, что начинаются раньше, чем заканчивается первая и получим задачу меньше исходной, для которой можно сделать аналогичные рассуждения.

Автокомментарий: текст был обновлен пользователем feruz.atamuradov (предыдущая версия, новая версия, сравнить).