Maximum Non-Overlapping Trips

You are given a set of trips, each represented as an interval \((s, e)\) where \(s\) is the start time and \(e\) is the end time. Your task is to select the maximum number of trips such that no two selected trips overlap. Two trips \((s_i, e_i)\) and \((s_j, e_j)\) are considered non-overlapping if \(s_j \ge e_i\) when \(i < j\). This problem can be solved using a greedy algorithm by sorting the trips based on their end times and then iteratively selecting trips that start after or at the end time of the last selected trip.

Mathematical Formulation:

Given a list of trips \(\{(s_i, e_i)\}_{i=1}^n\), find the largest subset \(\mathcal{S}\) such that for any two trips \((s_i, e_i)\) and \((s_j, e_j)\) in \(\mathcal{S}\) with \(i < j\), we have \(s_j \ge e_i\). Output the size of \(\mathcal{S}\).

inputFormat

The input is provided via standard input and has the following format:

• The first line contains a single integer (n), the number of trips.
• Each of the following (n) lines contains two space-separated integers representing the start time and end time of a trip.

outputFormat

Output a single integer via standard output representing the maximum number of non-overlapping trips.## sample

5
1 4
2 3
3 5
7 9
6 8

3