U598022 [Badcat题目合集]最长链

给定N个区间，每个区间有一个起点s_i和终点e_i。现在需要从中选择若干个区间组成一条"链"，满足任意两个相邻区间中，前一个区间的终点小于后一个区间的起点。 请计算这条链最多能包含多少个区间。

第一行包含一个整数N，表示区间的数量（1 ≤ N ≤ 1000）。 接下来N行，每行包含两个整数s_i和e_i，分别表示第i个区间的起点和终点（1 ≤ s_i < e_i ≤ 10^9）。

一行，一个整数，表示最长链包含的区间数量。