Maximizing Non-overlapping Rides

You are given n rides, each with a starting time and an ending time. A visitor can enjoy a ride only if its start time is not earlier than the ending time of the previously enjoyed ride. Your task is to determine the maximum number of rides a visitor can take without any overlaps.

Formally, given rides represented as intervals \([s_i, e_i]\) for \(i = 1, 2, \dots, n\), find the largest subset of rides such that for any two consecutive rides \((s_i, e_i)\) and \((s_j, e_j)\) in the subset, the condition \(s_j \ge e_i\) holds.

This is a classic activity selection problem that can be solved by greedily selecting rides that finish the earliest.

inputFormat

The input is read from stdin and has the following format:

n
s1 e1
s2 e2
... 
sn en

Where n is the number of rides, and each subsequent line contains two space-separated integers representing the start time and end time of a ride.

outputFormat

Output a single integer to stdout representing the maximum number of non-overlapping rides that can be enjoyed.

5
1 4
2 5
5 8
3 6
8 9

3