Maximum Non-overlapping Routes

You are given n routes, each defined by a pair of integers representing the start time and the end time of the route. A single driver can cover a route if the route does not overlap with any previously covered route. Two routes \((s_i, e_i)\) and \((s_j, e_j)\) are considered non-overlapping if \(s_j \ge e_i\). Your task is to determine the maximum number of non-overlapping routes that can be covered by a single driver.

Input Format: The first line contains an integer n indicating the number of routes. Each of the following n lines contains two space-separated integers s and e, the starting and ending times of a route respectively.

Output Format: Output a single integer representing the maximum number of non-overlapping routes.

The key idea is to sort the routes by their ending times. This greedy approach guarantees that you always choose the route which leaves the maximal room for the remaining routes. The condition for non-overlap is mathematically given by \(s_j \ge e_i\), where \(s_j\) is the starting time of the next route and \(e_i\) is the current route's ending time.

inputFormat

The input begins with an integer n (\(0 \leq n \leq 10^5\)), the number of routes. Each of the next n lines contains two integers \(s\) and \(e\) (\(0 \leq s < e \leq 10^9\)) representing the start time and end time of a route.

outputFormat

Output a single integer: the maximum number of non-overlapping routes that can be covered by a single driver.

5
1 3
2 5
3 9
6 8
8 10

3