Maximum Non-Overlapping Jobs

You are given n jobs, each defined by a start time and an end time. Your task is to select as many non-overlapping jobs as possible. Two jobs are considered overlapping if their time intervals intersect. An optimal solution can be obtained by a greedy approach: first, sort the jobs in increasing order of their finish times, and then select each job whose start time is greater than or equal to the finish time of the last selected job.

In formal terms, given a set of jobs \( I = \{(s_i, f_i)\}_{i=1}^n \), where \( s_i \) is the start time and \( f_i \) is the finish time of the \( i^{th} \) job, the algorithm sorts the jobs by \( f_i \) and selects jobs greedily. This strategy is optimal, as can be shown by an exchange argument.

inputFormat

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

n
s1 f1
s2 f2
... 
sn fn

Here, n (an integer) represents the number of jobs, and each of the following n lines contains two integers: the start time si and the finish time fi of the i-th job.

outputFormat

Output a single integer representing the maximum number of non-overlapping jobs that can be scheduled.

4
1 3
2 4
3 5
4 6

2