A student has
The student can attend a session only if it does not overlap in time with any other session they have already chosen to attend. Two sessions overlap if one starts before the other has ended; a session that starts exactly when another ends is allowed (they do not overlap).
Find the maximum number of non-overlapping sessions the student can attend.
The first line contains a single integer KaTeX can only parse string typed expression — the number of sessions.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the start and end time of the KaTeX can only parse string typed expression-th session.
Print a single integer — the maximum number of non-overlapping sessions that can be attended.
Input
4
1 3
2 4
3 5
6 83Choosing sessions KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression gives 3 non-overlapping sessions, which is optimal. The session KaTeX can only parse string typed expression must be skipped since it overlaps with both KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
Example 2:
Input
1
0 51With only one session available, the answer is simply 1.
Example 3:
Input
5
0 10
1 2
2 3
3 4
4 54The long session KaTeX can only parse string typed expression blocks out the entire timeline, so skipping it in favor of the four short back-to-back sessions KaTeX can only parse string typed expression gives a better result of 4.